题目背景

今天是快递员 Charles 的第一天工作。

题目描述

今天是快递员 Charles 的第一天工作。他需要派送 $N$ 个包裹，每个包裹都有一个标签编号，编号范围为 $1$ 到 $N$（不一定唯一）。每天结束时，他需要记录一个长度为 $N$ 的序列 $A$，其中 $A_i$ 是第 $i$ 个派送包裹的标签编号。

为了节省存储空间，Charles 决定使用差分编码记录一个长度为 $N-1$ 的序列 $D$，其中 $D_i = A_{i+1} - A_i$。

完成派送后，Charles 发现他不知道如何从 $D$ 恢复出 $A$。你的任务是帮助他恢复 $A$，或者判断是否无法唯一确定 $A$。

输入格式

• 第一行一个整数 $N$，表示包裹数量。
• 第二行一个长度为 $N-1$ 的整数序列 $D$，其中 $D_i$ 表示第 $i+1$ 个包裹和第 $i$ 个包裹标签编号的差。

输出格式

• 如果可以唯一恢复 $A$，输出 $N$ 个用空格分隔的整数，表示序列 $A$。
• 如果无法唯一恢复 $A$，输出 -1。

5
1 3 -2 1

1 2 5 3 4

5
2 2 -3 1

1 3 5 2 3

2
0

-1

提示

【样例解释】

对于样例 #1，差分序列 $D = [1, 3, -2, 1]$，恢复出的序列为 $A = [1, 2, 5, 3, 4]$，验证如下：

• $A_2 - A_1 = 2 - 1 = 1 = D_1$
• $A_3 - A_2 = 5 - 2 = 3 = D_2$
• $A_4 - A_3 = 3 - 5 = -2 = D_3$
• $A_5 - A_4 = 4 - 3 = 1 = D_4$

对于样例 #2，可以唯一恢复 $A = [1, 3, 5, 2, 3]$。

对于样例 #3，差分序列 $D = [0]$，序列可能为 $A = [1, 1]$ 或 $A = [2, 2]$，因此无法唯一恢复，输出 $-1$。

【数据范围】

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq N$
• $-N < D_i < N$