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

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

Для каждого элемента $$$a_i$$$ его тень $$$b_i$$$ — это сумма всех элементов массива $$$a$$$, которые строго меньше $$$a_i$$$. Формально:

$$$$$$b_i = \sum_{\substack{1 \le j \le n\\ a_j \lt a_i}} a_j$$$$$$

Вам дан массив теней $$$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$$$ ($$$0 \le b_i \le 2 \cdot 10^{14}$$$) — массив теней.

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — лексикографически минимальный корректный массив $$$a$$$, удовлетворяющий условию. Если корректного массива не существует, вместо этого выведите $$$-1$$$.

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

В первом наборе входных данных ответ — $$$a = [1]$$$. Поскольку в массиве только один элемент, строго меньших элементов нет, поэтому его тень равна $$$0$$$. Следовательно, $$$a=[1]$$$ корректен. Он также лексикографически минимален, потому что допустимы только положительные целые числа, а $$$1$$$ — наименьшее возможное значение.

Во втором наборе входных данных ответ — $$$a = [2,5,2,5,6]$$$:

  • Для каждого $$$2$$$ в массиве нет меньших элементов, поэтому тень равна $$$0$$$.
  • Для каждого $$$5$$$ строго меньшими элементами являются два числа $$$2$$$, поэтому тень равна $$$2+2=4$$$.
  • Для $$$6$$$ строго меньшими элементами являются два числа $$$2$$$ и два числа $$$5$$$, поэтому тень равна $$$2+2+5+5=14$$$.

Таким образом, массив теней в точности равен $$$b = [0,4,0,4,14]$$$.

В третьем наборе входных данных массив теней для $$$a = [3, 2, 2]$$$ вычисляется следующим образом:

  • Для $$$a_1 = 3$$$ строго меньшими элементами в массиве являются два $$$2$$$. Их сумма равна $$$2 + 2 = 4$$$. Значит, $$$b_1 = 4$$$.
  • Для $$$a_2 = 2$$$ строго меньших элементов в массиве нет. Значит, $$$b_2 = 0$$$.
  • Для $$$a_3 = 2$$$ строго меньших элементов в массиве нет. Значит, $$$b_3 = 0$$$.

Получившийся массив теней равен $$$b = [4, 0, 0]$$$, что совпадает с входными данными.