题目描述

江桥拿到了一个长为 $n$、仅由整数 $1$ 或 $2$ 组成的数组 $a = \{a_1,a_2,\dots,a_n \}$。

现在七萤想要让江桥将其重排得到数组 $a' = \{a'_1,a'_2,\dots,a'_n \}$，使得 $\sum\limits_{i = 1}^{n - 1}{\gcd \left(a'_i, a'_{i+1} \right) = k}$。

即所有相邻两个数的 $\gcd^\texttt{[1]}$ 之和恰好为 $k$。

请你帮帮江桥。

【名词解释】

$\gcd^\texttt{[1]}$：即最大公因数，指多个整数共有因数中最大的一个。例如，$12,18$ 和 $30$ 的公因数有 $1,2,3,6$，其中最大的因数是 $6$，因此 $\gcd(12,18,30)=6$。特别地，定义 $\gcd(0,x)=gcd(x,0) = x$。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,k$。 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，代表数组中的元素。

输出格式

对于每一组测试数据，新起一行。如果不存在满足条件的重排方案，直接输出 -1；否则，在一行上输出 $n$ 个整数，代表重排后的数组。如果存在多个重排方案，您可以输出任意一个。

1
4 4
1 2 1 2

1 2 2 1

1
4 4
1 1 1 2

-1

样例解释

在这个样例中：

$∙$ $\gcd(a_1,a_2)=\gcd(1,2)=1$；

$∙$ $\gcd(a_2,a_3)=\gcd(2,2)=2$；

$∙$ $\gcd(a_3,a_4)=\gcd(2,1)=1$。

数据规模与约定

下发文件

下发文件对应子任务 $5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10,2 \leq n,\sum n \leq 2 \times 10^5,0 \leq k \leq 2 \times n, \ a_i \in \{1,2\}$。