Problem Description

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.

Input Format

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$.

Output Format

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

2
3 2 1
2 6 4
4 2 3
7 3 6 9

2 4 6
3 6 9 21

Hint

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

The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.