32476번 - 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_1 , a_2 , \dots , a_N$ and $b_1 , b_2 , \dots , b_N$ are considered $K$-gcd equivalent if for every set of $K$ distinct indices from $1$ to $N$, the greatest common divisor (gcd) of the elements in these positions in both sequences is the same.

However, there’s a twist - you are allowed to multiply at most one element of $a$ by a given integer $X$ before finding this lowest $K$-gcd equivalent sequence. You are allowed to not multiply by $X$ at all and keep the same sequence. Additionally, it is guaranteed that $X$ is divisible by only $1$ and itself. You aim to minimize the resulting sequence lexicographically among all possible choices of preprocessing (or choosing not to) of $a$. Note that if you decide to preprocess the sequence, then your result must be a $K$-gcd equivalent of the preprocessed sequence $a$ (i.e. considering the greatest common divisors after the multiplication).

Write a program lex_gcd that solves this problem.

The first line of the input 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, output $N$ integers representing the lexicographically lowest $K$-gcd equivalent sequence to $a$ after performing the allowed preprocessing.

• $2 ≤ \sum{N} ≤ 10^5$ (over all test cases)
• $2 ≤ K ≤ N$
• $1 ≤ X ≤ 10^9$, $X$ is either $1$ or prime
• $1 ≤ a_i ≤ 10^9$