← 返回题目列表

Codeforces · 1739/B

B. 阵列恢复

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

对于大小为 $$$n$$$ 的非负整数数组 $$$a$$$,我们构造另一个数组 $$$d$$$,如下所示: $$$d_1 = a_1$$$, $$$d_i = |a_i - a_{i - 1}|$$$ for $$$2 \le i \le n$$$。

您的任务是从给定数组 $$$d$$$ 恢复数组 $$$a$$$,或者报告存在多个可能的数组。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 和 $$$d$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$ ($$$0 \le d_i \le 100$$$) — 数组 $$$d$$$ 的元素。

可以证明,在这些约束下,总是存在至少一个合适的数组$$$a$$$。

输出

对于每个测试用例,如果只有一个可能的数组 $$$a$$$,则打印数组 $$$a$$$ 的元素。否则,打印$$$-1$$$。

示例

输入 #1

3
4
1 0 2 5
3
2 6 3
5
0 0 0 0 0

输出 #1

1 1 3 8
-1
0 0 0 0 0

注意

在第二个示例中,有两个合适的数组:$$$[2, 8, 5]$$$ 和 $$$[2, 8, 11]$$$。