You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$ that Kristina originally had.

The second line of each test case contains exactly $n-1$ non-negative integer — elements of array $b$ ($0 \le b_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and that array $b$ was built correctly from some array $a$.

Output

For each test case on a separate line, print exactly $n$ non-negative integers — the elements of the array $a$ that Kristina originally had.

If there are several possible answers — output any of them.

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

Note

The first test case is explained in the problem statement.

In the second test case, we can get array $b$ = [$2, 2, 1$] from the array $a$ = [$2, 2, 1, 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$.

In the third test case, all elements of the array $b$ are zeros. Since each $b_i$ is the maximum of two adjacent elements of array $a$, array $a$ can only consist entirely of zeros.

In the fourth test case, we can get array $b$ = [$0, 3, 4, 4, 3$] from the array $a$ = [$0, 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$.