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

Массив целых чисел $$$p_1, p_2, \dots, p_n$$$ называется перестановкой, если он содержит каждое число от $$$1$$$ до $$$n$$$ ровно один раз. Например, следующие массивы являются перестановками: $$$[3, 1, 2]$$$, $$$[1]$$$, $$$[1, 2, 3, 4, 5]$$$ и $$$[4, 3, 1, 2]$$$. Следующие массивы перестановками не являются: $$$[2]$$$, $$$[1, 1]$$$, $$$[2, 3, 4]$$$.

Поликарп изобрел невероятно крутую перестановку $$$p_1, p_2, \dots, p_n$$$ длины $$$n$$$. К сожалению, он забыл эту перестановку. Единственное, что он помнит, это массив $$$q_1, q_2, \dots, q_{n-1}$$$ длины $$$n-1$$$, где $$$q_i=p_{i+1}-p_i$$$.

Заданы $$$n$$$ и $$$q=q_1, q_2, \dots, q_{n-1}$$$, помогите Поликарпу по этой информации восстановить придуманную им перестановку.

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

Первая строка содержит целое число $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — длину перестановки, которую надо восстановить. Следующая строка содержит $$$n-1$$$ целое число $$$q_1, q_2, \dots, q_{n-1}$$$ ($$$-n < q_i < n$$$).

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

Выведите -1, если перестановки длины $$$n$$$, которая соответствует массиву $$$q$$$, не существует. В противном случае выведите $$$p_1, p_2, \dots, p_n$$$. Если существует несколько подходящих перестановок, то выведите любую из них.

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