题目描述

给定一个长度为 $n$ 的序列 $a$ 和一个整数 $m$，保证序列 $a$ 中的每个元素均为不大于 $m$ 的正整数，且每个元素互不相等。

你需要构造一个长度为 $n$ 的序列 $b$，满足：

• 序列 $b$ 中的每个元素均为不大于 $m$ 的正整数；
• $\dfrac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{\sum\limits_{i=1}^n b_i}$ 为整数，即 $a_i$ 的权为 $b_i$ 时，序列 $a$ 的加权平均数为整数；
• 不存在有序三元整数组 $(i,j,k)$，满足 $1\le i<j<k\le n$ 且 $b_i=b_j=b_k$；

或报告无解。

输入格式

本题有多组测试数据。

第一行输入一个整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行输入两个整数 $n,m$。
• 第二行输入 $n$ 个整数，表示给定的序列 $a$。

输出格式

对于每组测试数据，输出一行：

• 若存在满足条件的序列 $b$，则输出用空格分隔的 $n$ 个整数，表示你构造的序列 $b$；
• 若不存在满足条件的序列 $b$，则输出 $-1$。

所有满足要求的输出均可通过。

3
3 5
1 2 3
2 2
1 2
4 100000
1 2 5 9

1 2 1
-1
1 1 3 4

提示

「样例解释 #1」

对于第 $1$ 组测试数据，给出的样例的加权平均数为 $\dfrac{1 \times 1+2 \times 2 + 3 \times 1}{1+2+1}=2$，为整数。

输出 1 5 1 也视作正确，其加权平均数为 $2$。

但是输出 1 6 1 不正确，虽然其加权平均数为 $2$，但是 $b_2>5$。

输出 1 2 3 也不正确，其加权平均数为 $\dfrac{7}{3}$，不为整数。

输出 1 1 1 也不正确，虽然其加权平均数为 $2$，但是存在有序三元组 $(1,2,3)$ 满足 $1 \leq 1 < 2 < 3 \leq 3$ 且 $b_1=b_2=b_3$。

对于第 $2$ 组测试数据，可以证明不存在满足条件的序列 $b$。

对于第 $3$ 组测试数据，给出的样例的加权平均数为 $\dfrac{1 \times 1+2 \times 1 + 5 \times 3+9 \times 4}{1+1+3+4}=6$，为整数。

「数据范围」

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有数据，$1 \le T \le 1000$，$1 \le n \le 10^6$，$1 \le a_i \le m \le 10^9$，$\sum n \le 10^6$，保证序列 $a$ 中的每个元素间互不相等。

只有你通过本题的所有测试点，你才能获得本题的分数。