B. Add 0 or K
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$ and a positive integer $$$k$$$.

In one operation, you may add either $$$0$$$ or $$$k$$$ to each $$$a_i$$$, i.e., choose another array of $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ where each $$$b_i$$$ is either $$$0$$$ or $$$k$$$, and update $$$a_i$$$ to $$$a_i + b_i$$$ for $$$1 \le i \le n$$$. Note that you can choose different values for each element of the array $$$b$$$.

Your task is to perform at most $$$k$$$ such operations to make $$$\gcd(a_1, a_2, \ldots, a_n) \gt 1$$$ $$$^{\text{∗}}$$$. It can be proved that this is always possible.

Output the final array after the operations. You do not have to output the operations themselves.

$$$^{\text{∗}}$$$$$$\gcd(a_1, a_2, \ldots, a_n)$$$ denotes the greatest common divisor (GCD) of $$$a_1, a_2, \ldots, a_n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the length of the array $$$a$$$ and the given constant.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output an array of $$$n$$$ integers in a new line — the final array after the operations. The integers in the output should be within the range from $$$1$$$ to $$$10^9 + k^2$$$.

If there are multiple valid outputs, you can output any of them.

Note that you do not have to minimize the number of operations.

Example
Input
8
3 3
2 7 1
4 5
2 9 16 14
4 1
1 2 3 4
5 2
5 6 7 8 9
2 10
7 9
1 1000000000
1
1 371
1000000000
3 6
1 3 5
Output
8 10 10
7 14 21 14
2 2 4 4
9 6 9 12 9
77 99
1000000000000000001
1000000000
25 15 5
Note

In the first test case, the output $$$[8,10,10]$$$ is valid because $$$\gcd(8, 10, 10) = 2 \gt 1$$$, and the array $$$[2, 7, 1]$$$ can be transformed into $$$[8, 10, 10]$$$ using at most $$$3$$$ operations. One possible sequence of operations is shown below:

Operation$$$b$$$Resulting $$$a$$$
$$$1$$$$$$[3,0,3]$$$$$$[5,7,4]$$$
$$$2$$$$$$[0,0,3]$$$$$$[5,7,7]$$$
$$$3$$$$$$[3,3,3]$$$$$$[8,10,10]$$$

Other outputs like $$$[2, 10, 4]$$$, $$$[8, 16, 4]$$$, and $$$[5, 10, 10]$$$ are also considered valid.

In the second test case, the output $$$[7, 14, 21, 14]$$$ is valid because:

  • $$$\gcd(7, 14, 21, 14) = 7 \gt 1$$$.
  • Starting from $$$[2, 9, 16, 14]$$$, applying the operation with $$$b = [5, 5, 5, 0]$$$ yields $$$[7, 14, 21, 14]$$$, requiring no more than $$$5$$$ operations.