← 返回题目列表

Codeforces · 1141/C

C. Polycarp 恢复排列

中文机器翻译题面 查看原题

如果整数数组 $$$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]$$$。

Polycarp 发明了一种非常酷的排列 $$$p_1, p_2, \dots, p_n$$$ 长度为 $$$n$$$。很失望,他却忘记了这个排列。他只记得长度为$$$n-1$$$的数组$$$q_1, q_2, \dots, q_{n-1}$$$,其中$$$q_i=p_{i+1}-p_i$$$。

给定 $$$n$$$ 和 $$$q=q_1, q_2, \dots, q_{n-1}$$$,帮助 Polycarp 恢复发明的排列。

输入

第一行包含整数 $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — 要恢复的排列的长度。第二行包含 $$$n-1$$$ 整数 $$$q_1, q_2, \dots, q_{n-1}$$$ ($$$-n < q_i < n$$$)。

输出

如果不存在对应于给定数组 $$$q$$$ 的长度 $$$n$$$ 的排列,则打印整数 -1。否则,如果存在,则打印 $$$p_1, p_2, \dots, p_n$$$。如果有很多这样的排列,则打印任何这样的排列。

示例

输入 #1

3
-2 1

输出 #1

3 1 2

输入 #2

5
1 1 1 1

输出 #2

1 2 3 4 5

输入 #3

4
-1 2 2

输出 #3

-1