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

Дан циклический массив $$$a$$$ из $$$n$$$ элементов, где $$$n$$$ — нечетное. За одну операцию вы можете сделать следующее:

  • Выберите индекс $$$1 \le i \le n$$$ и увеличьте $$$a_{i - 1}$$$ на $$$1$$$, $$$a_i$$$ на $$$2$$$ и $$$a_{i + 1}$$$ на $$$1$$$. Элемент перед первым элементом является последним элементом, так как это циклический массив.

Циклический массив называется сбалансированным, если все его элементы равны между собой.

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

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{6}$$$) — элементы массива $$$a$$$.

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

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

Для каждого набора входных данных:

  • Если невозможно сделать циклический массив сбалансированным, выведите $$$-1$$$.
  • В противном случае выведите $$$n$$$ целых чисел $$$v_1, v_2, \ldots, v_n$$$ ($$$0 \leq v_i \leq 10^{18}$$$) — где $$$v_i$$$ обозначает количество операций, примененных к индексу $$$i$$$. Можно доказать, что если существует какое-то решение, то существует решение при данных ограничениях. Если существует несколько решений при данных ограничениях, выведите любое из них.
Пример
Входные данные
6
3
2 1 2
3
1 2 3
5
1 2 1 2 1
7
1 2 1 2 1 3 1
9
10000 10000 10000 10000 10000 10001 10002 10001 10000
1
10
Выходные данные
0 1 0 
2 1 0 
2 0 3 0 2 
4 2 7 0 8 0 6 
1 1 1 1 1 1 0 1 1 
0
Примечание

В первом наборе входных данных:

  • После $$$1$$$ операции, примененной к индексу $$$i = 2$$$, массив $$$a = [3, 3, 3]$$$.

Во втором наборе входных данных:

  • После $$$2$$$ операций, примененных к индексу $$$i = 1$$$, массив $$$a = [5, 4, 5]$$$.
  • После $$$1$$$ операции, примененной к индексу $$$i = 2$$$, массив $$$a = [6, 6, 6]$$$.

В третьем наборе входных данных:

  • После $$$2$$$ операций, примененных к индексу $$$i = 1$$$, массив $$$a = [5, 4, 1, 2, 3]$$$.
  • После $$$3$$$ операций, примененных к индексу $$$i = 3$$$, массив $$$a = [5, 7, 7, 5, 3]$$$.
  • После $$$2$$$ операций, примененных к индексу $$$i = 5$$$, массив $$$a = [7, 7, 7, 7, 7]$$$.