LEX_GCD

Task

Your task is to find the lexicographically lowest $K$-gcd equivalent 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 $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 that solves this problem.

Input data

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 data

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

Constraints and clarifications

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

• Points for a given subtask are awarded only if all tests specified for it are successfully passed.

Example

stdin

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

stdout

2 4 6
3 6 9 21

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