该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：array.in

输出：array.out

题目描述

Kristina 有一个包含 $n$ 个非负整数的数组 $a$。

她构造了一个长度为 $n - 1$ 的新数组 $b$，使得 $ b_i = \max(a_i, a_{i + 1}) \text{ } (1 \le i \le n - 1) $。

例如，假设 Kristina 有一个长度为 $5$ 的数组 $a = [ 3, 0, 4, 0, 5 ]$，则她将以以下方式构造数组 $b$：

1. $b_1 = \max(a_1, a_2) = \max(3, 0) = 3;$
2. $b_2 = \max(a_2, a_3) = \max(0, 4) = 4;$
3. $b_3 = \max(a_3, a_4) = \max(4, 0) = 4;$
4. $b_4 = \max(a_4, a_5) = \max(0, 5) = 5.$

所以，她得到了一个长度为 $4$ 的数组 $b = [ 3, 4, 4, 5 ]$。

现在，你只知道数组 $b$。你需要找出任意一个可能的数组 $a$。

输入格式

输入数据的第一行包含一个整数 $t \text{ } (1 \le t \le 10 ^ 4)$，代表测试数据组数。

每组测试数据的第一行包含一个整数 $n \text{ } (1 \le n \le 2 \times 10 ^ 5)$，代表数组 $a$ 的长度。

每组测试数据的第二行包含 $n - 1$ 个非负整数，代表数组 $b$ 的各个元素 $(0 \le b_i \le 10^9)$。

对于每个测试点，保证所有 $t$ 组测试数据中 $n$ 的总和不超过 $2 \times 10 ^ 5$，且保证有解。

输出格式

对于每组测试数据，在同一行内输出 $n$ 个非负整数，代表数组 $a$ 的元素，元素与元素之间以空格隔开。

如果有多种可能的答案，输出任意一种即可。

输入输出样例

11
5
3 4 4 5
4
2 2 1
5
0 0 0 0
6
0 3 4 4 3
2
10
4
3 3 3
5
4 2 5 5
4
3 3 3
4
2 1 0
3
4 4
6
8 1 3 5 10

3 0 4 0 5
2 2 1 1
0 0 0 0 0
0 0 3 4 3 3
10 10
3 3 3 1
4 2 2 5 5
3 3 3 3
2 1 0 0
2 4 4
8 1 1 3 5 10

样例解释

对于第二组测试数据，我们可以从 $a = [ 2, 2, 1, 1 ]$ 推出 $b = [ 2, 2, 1 ]$：

• $b_1 = \max(a_1, a_2) = \max(2, 2) = 2;$
• $b_2 = \max(a_2, a_3) = \max(2, 1) = 2;$
• $b_3 = \max(a_3, a_4) = \max(1, 1) = 1.$

对于第三组测试数据，数组 $b$ 中的所有元素均为 $0$，因为 $b$ 中的每个元素均为 $a$ 中两个相邻元素的最大值，所以数组 $a$ 中的每个元素均为 $0$。

对于第四组测试数据，我们可以从 $a = [ 0, 0, 3, 4, 3, 3 ]$ 推出 $b = [ 0, 3, 4, 3, 3 ]$：

• $b_1 = \max(a_1, a_2) = \max(0, 0) = 0;$
• $b_2 = \max(a_2, a_3) = \max(0, 3) = 3;$
• $b_3 = \max(a_3, a_4) = \max(3, 4) = 4;$
• $b_4 = \max(a_4, a_5) = \max(4, 3) = 4;$
• $b_5 = \max(a_5, a_6) = \max(3, 3) = 3.$