Problem Description

Given a sequence $a$ of length $n$ and an integer $m$, it is guaranteed that every element in $a$ is a positive integer not greater than $m$, and all elements are pairwise distinct.

You need to construct a sequence $b$ of length $n$ such that:

• Every element in $b$ is a positive integer not greater than $m$.
• $\dfrac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{\sum\limits_{i=1}^n b_i}$ is an integer. That is, when the weight of $a_i$ is $b_i$, the weighted mean of sequence $a$ is an integer.
• There does not exist an ordered triple of integers $(i,j,k)$ such that $1\le i<j<k\le n$ and $b_i=b_j=b_k$.

Or report that there is no solution.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, which denotes the number of test cases.

Then each test case is given as follows:

• The first line contains two integers $n,m$.
• The second line contains $n$ integers, representing the given sequence $a$.

Output Format

For each test case, output one line:

• If there exists a sequence $b$ that satisfies the conditions, output $n$ integers separated by spaces, representing the sequence $b$ you constructed.
• If no such sequence $b$ exists, output $-1$.

Any output that satisfies the requirements will be accepted.

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

1 2 1
-1
1 1 3 4

Hint

"Sample Explanation #1"

For the $1$st test case, the weighted mean of the sample output is $\dfrac{1 \times 1+2 \times 2 + 3 \times 1}{1+2+1}=2$, which is an integer.

Output 1 5 1 is also considered correct, and its weighted mean is $2$.

However, output 1 6 1 is incorrect. Although its weighted mean is $2$, it has $b_2>5$.

Output 1 2 3 is also incorrect, because its weighted mean is $\dfrac{7}{3}$, which is not an integer.

Output 1 1 1 is also incorrect. Although its weighted mean is $2$, there exists an ordered triple $(1,2,3)$ such that $1 \leq 1 < 2 < 3 \leq 3$ and $b_1=b_2=b_3$.

For the $2$nd test case, it can be proven that no sequence $b$ satisfying the conditions exists.

For the $3$rd test case, the weighted mean of the sample output is $\dfrac{1 \times 1+2 \times 1 + 5 \times 3+9 \times 4}{1+1+3+4}=6$, which is an integer.

Constraints

Let $\sum n$ denote the sum of $n$ within a single test file.

For all testdata, $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$. It is guaranteed that all elements in sequence $a$ are pairwise distinct.

You can get the score for this problem only if you pass all test points.

Translated by ChatGPT 5