[AdditionalFile5242.zip](file://AdditionalFile5242.zip?type=additional_file)

#5242. 「NOISG 2020 Final」Labels

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2020 Final T1. Labels

今天是快递员查尔斯的第一天工作。他被分配了运送 $N$ 个包裹，每个包裹上有一个（不一定唯一）介于 $1$ 到 $N$ 之间的标签编号。每天结束时，他需要报告一个包含 $N$ 个整数的序列 $A$，即 $A_1, \ldots, A_N$，其中 $A_i$ 是第 $i$ 个送达包裹的标签编号。

作为一名热爱数学的人，查尔斯决定使用差值编码来节省内存空间，并记录了一个包含 $N-1$ 个整数的序列 $D$，即 $D_1, \ldots, D_{N-1}$，其中 $D_i = A_{i+1} - A_i$。

在送完所有包裹后，查尔斯意识到他不知道如何从 $D$ 恢复 $A$。你的任务是帮助他恢复 $A$，或者说明无法唯一恢复 $A$。

输入格式

程序需从标准输入读取数据。

第一行包含一个整数 $N$，表示包裹总数。

第二行包含 $N-1$ 个空格分隔的整数 $D_1, \ldots, D_{N-1}$，其中 $D_i$ 表示第 $(i+1)$ 个送达包裹与第 $i$ 个送达包裹的标签编号之差。

输出格式

程序需向标准输出输出结果。

如果可以从 $D$ 唯一恢复 $A$，输出 $N$ 个空格分隔的整数，表示序列 $A$。

否则，输出一行，包含单个整数 $-1$。

样例 1

输入

5
1 3 -2 1

输出

1 2 5 3 4

可以唯一恢复 $A = [1, 2, 5, 3, 4]$。

这与 $D$ 一致，因为：

$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, 3, 5$ 的限制。

样例 2

输入

5
2 2 -3 1

输出

1 3 5 2 3

可以唯一恢复 $A = [1, 3, 5, 2, 3]$。注意，标签编号可以出现多次。

这个样例满足子任务 $2, 3, 5$ 的限制。

样例 3

输入

2
0

输出

-1

这个样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示：