题目描述

给定一个由 N 个正整数组成的序列 a_1, a_2, ..., a_N。你需要找出它的一个字典序最小的 K-gcd 等价排列。

如果两个序列 a_1, a_2, ..., a_N 和 b_1, b_2, ..., b_N 互为排列，并且满足：

• 对于任意一组由 K 个不同下标组成的集合；
• 取出这 K 个位置上的元素；
• 在两个序列中，这 K 个元素的最大公约数（gcd）都相同；

那么这两个序列就被称为 K-gcd 等价。

不过这里还有一个额外操作：在寻找答案之前，你最多可以选择一个元素，将其乘以给定整数 X。

• 你也可以选择不进行任何乘法操作；
• 保证 X 要么等于 1，要么是一个质数；
• 如果你选择先进行乘法预处理，那么最终输出的序列必须是预处理之后序列的一个 K-gcd 等价排列。

你的目标是在所有允许的预处理方式中，使最终得到的 K-gcd 等价排列的字典序最小。

输入格式

第一行一个整数 T，表示测试组数。

接下来每组测试包含：

• 一行三个正整数 N, K, X
• 一行 N 个正整数 a_1, a_2, ..., a_N

输出格式

对于每组测试，输出 N 个整数，表示在允许预处理之后，字典序最小的 K-gcd 等价序列。

约束条件

• 2 <= sum N <= 10^5（所有测试组的 N 之和）
• 2 <= K <= N
• 1 <= X <= 10^9，且 X 要么为 1，要么为质数
• 1 <= a_i <= 10^9

子任务

只有当某个子任务以及其要求的所有前置子任务全部通过时，才能获得该子任务的分数。

样例

输入

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

输出

2 4 6
3 6 9 21

说明

共有两组测试。

• 对于第一组，不需要做任何预处理。因为所有二元组的 gcd 都保持为 2，所以答案是 2 4 6。
• 对于第二组，将第一个元素乘以 3 后，得到的字典序最小 K-gcd 等价排列为 3 6 9 21。