P16392 [IATI 2024] Lex_gcd

Your task is to find the lexicographically lowest $K$-gcd equivalent $\textbf{permutation}$ of a given sequence of $N$ positive integers $a_1, a_2, \ldots, a_N$. Two sequences (that are permutations of each other) $a_1, a_2, \ldots, a_N$ and $b_1, b_2, \ldots, 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 $\textbf{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$. Write a program $\texttt{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, \ldots, a_N$.

For each test case, output $N$ integers representing the lexicographically lowest $K$-gcd equivalent sequence to $a$ after performing the allowed preprocessing.

### Explanation Two test cases. For the first one, no preprocessing is required. The $K$-gcd property is satisfied since the greatest common divisor of all pairs remains 2. For the second one, preprocessing by multiplying the first element by $3$ results in the lexicographically lowest sequence $3, 6, 9, 21$. ### Constraints - $2 \leq \sum_{}{} N \leq 10^5$ (over all test cases) - $2 \leq K \leq N$ - $1 \leq X \leq 10^9$, $X$ is either $1$ or prime - $1 \leq a_i \leq 10^9$ ### Subtasks | **Subtask** | **Points** | **Required subtasks** | **$N$** | **$X$** | **Other constraints** | | :---: | :---: | :---: | :---: | :---: | :---: | | $1$ | $6$ | $-$ | $\sum N \leq 5$ | $X = 1$ | $-$ | | $2$ | $19$ | $1$ | $\sum N \leq 1000$ | $X = 1$ | $-$ | | $3$ | $13$ | $1-2$ | $\sum N \leq 10^5$ | $X = 1$ | $-$ | | $4$ | $4$ | $1$ | $\sum N \leq 100$ | $-$ | $-$ | | $5$ | $4$ | $1,2,4$ | $\sum N \leq 1000$ | $-$ | $-$ | | $6$ | $31$ | $-$ | $\sum N \leq 10^5$ | $-$ | $a_i \neq a_j$ for $i \neq j$ | | $7$ | $23$ | $1-6$ | $\sum N \leq 10^5$ | $-$ | $-$ | The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.