LEX_GCD

Your task is to find the lexicographically lowest $K$-gcd equivalent permutation of a given sequence of $N$ positive integers $a\_1 , a\_2 , \dots , a\_N$. Two sequences that are permutations of each other, $a$ and $b$, are $K$-gcd equivalent if, for every set of $K$ distinct indices from $1$ to $N$, the gcd of the elements at those positions is the same in both sequences.

You may multiply at most one element of $a$ by a given integer $X$ before searching. You may also leave $a$ unchanged. $X$ is either $1$ or a prime, so its only divisors are $1$ and $X$. If you multiply an element, the result must be a $K$-gcd equivalent of the modified $a$, with the gcds computed after the multiplication.

The first line contains one integer $T$, the number of test cases. Each test case consists of three positive integers $N$, $K$, and $X$, followed by $N$ positive integers $a\_1 , a\_2 , \dots , a\_N$.

For each test case, print $N$ integers: the lexicographically lowest $K$-gcd equivalent sequence of $a$ after the optional preprocessing.

• $2 \le \sum N \le 10^5$ (over all test cases)
• $2 \le K \le N$
• $1 \le X \le 10^9$, and $X$ is either $1$ or prime
• $1 \le a\_i \le 10^9$