CF2134B Add 0 or K

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) > 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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of $$$a_1, a_2, \ldots, a_n$$$.

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$$$.

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.

In the first test case, the output $$$[8,10,10]$$$ is valid because $$$\gcd(8, 10, 10) = 2 > 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 > 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.