B. Добавить 0 или K
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из $$$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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ целых чисел — финальный массив после операций.

Если существует несколько ответов, вы можете вывести любой из них.

Обратите внимание, что вам не нужно минимизировать количество операций.

Пример
Входные данные
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
Выходные данные
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]$$$ можно преобразовать в $$$[8, 10, 10]$$$ с использованием не более чем $$$3$$$ операций. Одна из возможных последовательностей операций показана ниже:

Операция$$$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$$$ операций.