Условие:
Вам дан массив из n целых положительных чисел a1,a2,…,an и целое положительное число k.
За одну операцию вы можете добавить либо 0, либо k к каждому ai, т.е. выбрать другой массив из n целых чисел b1,b2,…,bn, где каждое bi равно либо 0, либо k, и сделать ai равным ai+bi для всех 1≤i≤n. Обратите внимание, что вы можете выбирать разные значения для каждого элемента массива b.
Ваша задача — выполнить не более k таких операций, чтобы сделать gcd(a1,a2,…,an)>1. Можно доказать, что это всегда возможно.
Выведите финальный массив после применения операций. Вам не нужно выводить сами операции.
\ngcd(a1,a2,…,an) обозначает наибольший общий делитель (НОД) a1,a2,…,an.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤1000) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа n и k (1≤n≤105, 1≤k≤109) — длина массива a и заданная константа.
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (1≤ai≤109) — элементы массива a.
Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 105.
Выходные данные
Для каждого набора входных данных выведите на отдельной строке массив из n целых чисел — финальный массив после операций.
Если существует несколько ответов, вы можете вывести любой из них.
Обратите внимание, что вам не нужно минимизировать количество операций.
