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

У Юсефа есть скрытый массив $$$a$$$ длины $$$n$$$, состоящий целиком из строго положительных целых чисел.

Одна операция была выполнена ровно один раз, чтобы создать массив $$$b$$$:

  • Присвоим $$$b_1 = a_1$$$.
  • Для каждого $$$i$$$ от $$$2$$$ до $$$n$$$ присвоим $$$b_i = a_i - a_{i-1}$$$.
  • После этого элементы массива $$$b$$$ были полностью перемешаны.

Вам дан перемешанный массив $$$b$$$. Восстановите лексикографически наименьший исходный массив $$$a$$$. Если для любого расположения элементов $$$b$$$ невозможно получить массив $$$a$$$, состоящий из строго положительных целых чисел, выведите $$$-1$$$.

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

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

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

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — элементы перемешанного массива $$$b$$$.

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

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

Для каждого набора входных данных выведите $$$n$$$ строго положительных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \ge 1$$$) — лексикографически наименьший исходный массив $$$a$$$. Если построить корректный массив $$$a$$$ невозможно, вместо этого выведите $$$-1$$$.

Пример
Входные данные
8
1
5
4
-5 2 1 1
6
-3 4 2 -1 1 0
6
-2 -2 4 1 0 1
7
0 0 -2 3 0 -1 2
8
-1 -1 -1 -1 5 0 0 1
5
1000000000 500000000 750000000 100000000 900000000
10
1000000000 -1000000000 500000000 -500000000 1 1 -1 -1 2 -2
Выходные данные
5 
-1
1 1 3 2 6 3 
1 1 2 6 4 2 
2 1 1 1 1 4 2 
1 1 1 6 5 4 3 2 
100000000 600000000 1350000000 2250000000 3250000000 
-1
Примечание

В первом наборе входных данных единственный корректный массив — это $$$a = [5]$$$.

Во втором наборе входных данных не существует корректного расположения элементов массива $$$b$$$, которое восстанавливает массив $$$a$$$, состоящий целиком из строго положительных целых чисел. Поэтому ответ — $$$-1$$$.

В третьем наборе входных данных одно из корректных расположений восстанавливает массив $$$a=[1,1,3,2,6,3]$$$. Получающаяся последовательность $$$[1, 0, 2, -1, 4, -3]$$$ разностей является перестановкой заданного массива $$$b$$$, и среди всех корректных восстановлений этот массив лексикографически наименьший.