今天是快递员 Charles 上班的第一天。他被要求配送 $N$ 个包裹，每个包裹都有一个介于 $1$ 到 $N$ 之间（包括 $1$ 和 $N$，且不一定唯一）的标签编号。在每天结束时，他需要报告一个由 $N$ 个整数组成的序列 $A = A_1, \dots, A_N$，其中 $A_i$ 是第 $i$ 个送达包裹的标签编号。

Charles 本质上是个数学家，为了节省内存空间，他决定使用差分编码，转而记录一个由 $N - 1$ 个整数组成的序列 $D = D_1, \dots, D_{N-1}$，其中 $D_i = A_{i+1} - A_i$。

在送完所有包裹后，Charles 意识到他不知道如何从 $D$ 中恢复出 $A$。你今天的任务是帮助他，或者指出无法唯一地恢复出 $A$。

输入格式

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

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

输出格式

如果可以唯一地从 $D$ 中恢复出 $A$，你的输出应该包含 $N$ 个空格分隔的整数，即序列 $A$。

否则，你的输出应该在单行中包含一个整数 -1。

实现细节

由于子任务 4 和 5 的输入长度可能非常大，建议你使用带有快速输入例程的 C++ 来解决此问题。

附件中提供了包含快速输入/输出模板的 C++ 和 Java 源文件。强烈建议你使用这些模板。

如果你使用 Java 实现解决方案，请将文件命名为 Labels.java，并将主函数放在 Labels 类中。

子任务

对于所有测试用例，输入将满足以下范围：

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

你的程序将在满足以下限制的输入实例上进行测试：

样例

输入样例 1

5
1 3 -2 1

输出样例 1

1 2 5 3 4

说明 1

该测试用例仅对子任务 2、3 和 5 有效。

我们可以唯一地恢复出 $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

5
2 2 -3 1

输出样例 2

1 3 5 2 3

说明 2

该测试用例仅对子任务 2、3 和 5 有效。

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

输入样例 3

2
0

输出样例 3

-1

说明 3

该测试用例对所有子任务均有效。

我们无法唯一地恢复出 $A$，因为我们可能会得到 $A = [1, 1]$ 或 $A = [2, 2]$。