LEX_GCD

주어진 양의 정수 $N$개의 수열 $a\_1 , a\_2 , \dots , a\_N$에 대해, 사전순으로 가장 작은 $K$-gcd 동치 순열을 구하세요. 서로 순열 관계에 있는 두 수열 $a$와 $b$는, 1부터 $N$까지의 인덱스 중 서로 다른 $K$개를 고를 때마다 그 위치의 원소들의 gcd가 두 수열에서 같으면 $K$-gcd 동치입니다.

탐색하기 전에 $a$의 원소 중 최대 하나에 주어진 정수 $X$를 곱할 수 있습니다. 곱하지 않고 그대로 둘 수도 있습니다. $X$는 1 또는 소수이므로 약수는 1과 $X$뿐입니다. 원소를 곱했다면, 결과는 곱한 뒤의 $a$에 대한 $K$-gcd 동치 수열이어야 하며 gcd도 곱한 뒤의 값으로 계산합니다.

첫 줄에 테스트 케이스 수 $T$가 주어집니다. 각 테스트 케이스는 정수 $N$, $K$, $X$와 이어서 주어지는 양의 정수 $N$개 $a\_1 , a\_2 , \dots , a\_N$로 이루어집니다.

각 테스트 케이스마다, 선택적 전처리를 거친 $a$에 대한 사전순 최소 $K$-gcd 동치 수열의 정수 $N$개를 출력합니다.

• $2 \le \sum N \le 10^5$ (모든 테스트 케이스의 합)
• $2 \le K \le N$
• $1 \le X \le 10^9$, $X$는 1 또는 소수
• $1 \le a\_i \le 10^9$