← 返回题目列表

Codeforces · 1968/C

C. 通过余数组装

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

给你一个数组 $$$x_2,x_3,\dots,x_n$$$。您的任务是找到任意数组 $$$a_1,\dots,a_n$$$,其中:

- $$$1\le a_i\le 10^9$$$ 对于所有 $$$1\le i\le n$$$。
- $$$x_i=a_i \bmod a_{i-1}$$$ 对于所有 $$$2\le i\le n$$$。

这里 $$$c\bmod d$$$ 表示整数 $$$c$$$ 除以整数 $$$d$$$ 的余数。例如$$$5 \bmod 2 = 1$$$、$$$72 \bmod 3 = 0$$$、$$$143 \bmod 14 = 3$$$。

注意,如果有多个 $$$a$$$ 满足该语句,则允许查找任何一个。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2\le n\le 500)$$$ - $$$a$$$ 中的元素数量。

每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$x_2,\dots,x_n$$$ $$$(1\le x_i\le 500)$$$ — $$$x$$$ 的元素。

保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出任何满足语句的 $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) 。

示例

输入 #1

5
4
2 4 1
3
1 1
6
4 2 5 1 2
2
500
3
1 5

输出 #1

3 5 4 9
2 5 11
5 14 16 5 11 24
501 500
2 7 5

注意

在第一个测试用例中 $$$a=[3,5,4,9]$$$ 满足条件,因为:

- $$$a_2\bmod a_1=5\bmod 3=2=x_2$$$;
- $$$a_3\bmod a_2=4\bmod 5=4=x_3$$$;
- $$$a_4\bmod a_3=9\bmod 4=1=x_4$$$;