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

Для массива целых неотрицательных чисел $$$a$$$ размера $$$n$$$ выписали массив $$$d$$$, где $$$d_1 = a_1$$$, $$$d_i = |a_i - a_{i - 1}|$$$ для $$$2 \le i \le n$$$.

Ваша задача — по заданному массиву $$$d$$$ восстановить массив $$$a$$$, или сообщить, что подходящих массивов несколько.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — размер массивов $$$a$$$ и $$$d$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$0 \le d_i \le 100$$$) — элементы массива $$$d$$$.

Можно показать, что при таких ограничениях всегда существует хотя бы один подходящий массив $$$a$$$.

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

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

Пример
Входные данные
3
4
1 0 2 5
3
2 6 3
5
0 0 0 0 0
Выходные данные
1 1 3 8
-1
0 0 0 0 0
Примечание

Во втором примере есть два подходящих массива: $$$[2, 8, 5]$$$ и $$$[2, 8, 11]$$$.