给定一个由 $$$n$$$ 正整数 $$$a_1、a_2、\ldots、a_n$$$ 和一个正整数 $$$k$$$ 组成的数组。
在一次操作中,您可以将 $$$0$$$ 或 $$$k$$$ 添加到每个 $$$a_i$$$,即,选择另一个 $$$n$$$ 整数 $$$b_1、b_2、\ldots、b_n$$$ 数组,其中每个 $$$b_i$$$ 是 $$$0$$$ 或 $$$k$$$,然后更新$$$a_i$$$ 到 $$$a_i + b_i$$$,$$$1 \le i \le n$$$。请注意,您可以为数组 $$$b$$$ 的每个元素选择不同的值。
你的任务是执行至多$$$k$$$这样的操作来使$$$\gcd(a_1, a_2, \ldots, a_n) \gt 1$$$ $$$^{\text{*}}$$$。可以证明,这总是可能的。
输出运算后的最终数组。你做的 不 必须输出操作本身。
$$$^{\text{*}}$$$$$$\gcd(a_1, a_2, \ldots, a_n)$$$ 表示 $$$a_1, a_2, \ldots, a_n$$$ 的最大公约数 (GCD)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \leq k \leq 10^9$$$) - 数组 $$$a$$$ 的长度和给定常量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在新行中输出 $$$n$$$ 整数的数组 - 操作后的最终数组。输出中的整数应在 $$$1$$$ 到 $$$10^9 + k^2$$$ 的范围内。
如果有多个有效输出,则可以输出其中任何一个。
请注意,您这样做 不 必须尽量减少操作次数。
示例
输入复制
83 32 7 14 52 9 16 144 11 2 3 45 25 6 7 8 92 107 91 100000000011 37110000000003 61 3 5
输出复制
8 10 10 7 14 21 14 2 2 4 4 9 6 9 12 9 77 99 1000000000000000001 1000000000 25 15 5
注意
在第一个测试用例中,输出 $$$[8,10,10]$$$ 有效,因为 $$$\gcd(8, 10, 10) = 2 \gt 1$$$,并且数组 $$$[2, 7, 1]$$$ 最多可以使用 $$$3$$$ 操作转换为 $$$[8, 10, 10]$$$。一种可能的操作顺序如下所示:
| 操作 | $$$b$$$ | 结果$$$a$$$ |
| $$$1$$$ | $$$[3,0,3]$$$ | $$$[5,7,4]$$$ |
| $$$2$$$ | $$$[0,0,3]$$$ | $$$[5,7,7]$$$ |
| $$$3$$$ | $$$[3,3,3]$$$ | $$$[8,10,10]$$$ |
其他输出,如 $$$[2, 10, 4]$$$、$$$[8, 16, 4]$$$ 和 $$$[5, 10, 10]$$$ 也被认为是有效的。
在第二个测试用例中,输出 $$$[7, 14, 21, 14]$$$ 有效,因为:
- $$$\gcd(7, 14, 21, 14) = 7 \gt 1$$$。
- 从 $$$[2, 9, 16, 14]$$$ 开始,应用 $$$b = [5, 5, 5, 0]$$$ 的运算得到 $$$[7, 14, 21, 14]$$$,需要不超过 $$$5$$$ 运算。