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

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

• Each element in sequence $b$ is a positive integer no greater than $m$;
• $\dfrac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{\sum\limits_{i=1}^n b_i}$ is an integer, meaning the weighted average of sequence $a$ with weights $b_i$ 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 no such sequence exists.

Input

This problem contains multiple test cases.

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

The following lines describe the test cases. For each test case:

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

Output

For each test case, output one line:

• If a sequence $b$ satisfying the conditions exists, output $n$ space-separated integers representing your constructed sequence $b$;
• If no such sequence $b$ exists, output $-1$.

Any output that satisfies the requirements will be accepted.

Examples

Input 1

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

Output 1

1 2 1
-1
1 1 3 4

Note

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

Outputting 1 5 1 is also considered correct, as its weighted average is $2$.

However, outputting 1 6 1 is incorrect because, although the weighted average is $2$, $b_2 > 5$.

Outputting 1 2 3 is also incorrect because the weighted average is $\dfrac{7}{3}$, which is not an integer.

Outputting 1 1 1 is also incorrect because, although the weighted average is $2$, there exists an ordered triple $(1, 2, 3)$ such that $1 \le 1 < 2 < 3 \le 3$ and $b_1 = b_2 = b_3$.

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

For the third test case, the weighted average of the provided 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$ over all test cases.

For all data, $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 distinct.