Kristina 有一个长度为 $$$n$$$ 的数组 $$$a$$$,由非负整数组成。
她构建了一个长度为 $$$n-1$$$ 的新数组 $$$b$$$,使得 $$$b_i = \max(a_i, a_{i+1})$$$ ($$$1 \le i \le n-1$$$)。
例如,假设 Kristina 有一个长度为 $$$5$$$ 的数组 $$$a$$$ = [$$$3, 0, 4, 0, 5$$$]。然后她做了以下事情:
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$$$。
你只知道数组$$$b$$$。查找 Kristina 最初可能拥有的任何匹配数组 $$$a$$$。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — Kristina 最初拥有的数组 $$$a$$$ 中的元素数量。
每个测试用例的第二行恰好包含 $$$n-1$$$ 非负整数 — 数组 $$$b$$$ 的元素 ($$$0 \le b_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,并且数组 $$$b$$$ 是从某个数组 $$$a$$$ 正确构建的。
输出
对于单独一行上的每个测试用例,精确打印 $$$n$$$ 非负整数 - Kristina 最初拥有的数组 $$$a$$$ 的元素。
如果有多个可能的答案 - 输出其中任何一个。
示例
输入 #1
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
输出 #1
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$$$ 的所有元素均为零。由于每个 $$$b_i$$$ 是数组 $$$a$$$ 中两个相邻元素的最大值,因此数组 $$$a$$$ 只能完全由零组成。
在第四个测试用例中,我们可以从数组 $$$a$$$ = [$$$0, 0, 3, 4, 3, 3$$$] 得到数组 $$$b$$$ = [$$$0, 3, 4, 4, 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$$$。