P11332 [NOISG 2020 Finals] Labels

今天是快递员 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`。

【样例解释】 对于样例 #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$ | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $1$ | $7$ | $N = 2$ | | $2$ | $15$ | $2 \leq N \leq 6$ | | $3$ | $25$ | $2 \leq N \leq 10^3$ | | $4$ | $18$ | $-1 \leq D_i \leq 1$ | | $5$ | $35$ | 无额外限制 |