D. Замены в массиве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$.

Вы можете выполнить следующую операцию любое количество раз (в том числе ноль):

  • Выбрать индекс $$$i$$$ ($$$2 \le i \le n - 1$$$) таким образом, чтобы $$$a_{i - 1}$$$ и $$$a_{i + 1}$$$ имели одинаковую четность.
  • Заменить $$$a_i$$$ на $$$a_{i - 1} - a_i + a_{i + 1}$$$.

Найдите лексикографически наименьший массив, который можно получить после любого количества операций.

Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$ той же длины тогда и только тогда, когда в первой позиции, в которой $$$x$$$ и $$$y$$$ различаются, элемент в $$$x$$$ строго меньше соответствующего элемента в $$$y$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел — лексикографически наименьший массив, который можно получить.

Пример
Входные данные
3
10
100 108 114 118 120 5 7 19 13 11
3
1 2 3
4
10 10 8 4
Выходные данные
100 102 106 112 120 5 -1 -3 -1 11 
1 2 3 
10 6 4 4
Примечание

Во втором наборе входных данных исходный массив имеет вид $$$[1, 2, 3]$$$. Единственным допустимым индексом для выбора является $$$i = 2$$$, поскольку $$$a_1 = 1$$$ и $$$a_3 = 3$$$ имеют одинаковую четность. Замена $$$a_2$$$ на $$$1 - 2 + 3 = 2$$$ не изменяет массив. Таким образом, минимальным массивом является $$$[1, 2, 3]$$$.

В третьем наборе входных данных исходный массив равен $$$[10, 10, 8, 4]$$$. Мы можем выполнить следующую последовательность операций:

  • Выберем $$$i = 2$$$ (элементы $$$a_1 = 10$$$ и $$$a_3 = 8$$$ оба четные). Заменить $$$a_2$$$ на $$$10 - 10 + 8 = 8$$$. Массив принимает вид $$$[10, 8, 8, 4]$$$.
  • Выбрать $$$i = 3$$$ (элементы $$$a_2 = 8$$$ и $$$a_4 = 4$$$ оба чётные). Заменить $$$a_3$$$ на $$$8 - 8 + 4 = 4$$$. Массив принимает вид $$$[10, 8, 4, 4]$$$.
  • Выберем $$$i = 2$$$ ($$$a_1 = 10$$$ и $$$a_3 = 4$$$ — оба чётные). Заменим $$$a_2$$$ на $$$10 - 8 + 4 = 6$$$. Массив принимает вид $$$[10, 6, 4, 4]$$$.
Можно показать, что $$$[10, 6, 4, 4]$$$ — это лексикографически наименьший из возможных массивов.