You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Kristina had an array $$$a$$$ of length $$$n$$$ consisting of non-negative integers.

She built a new array $$$b$$$ of length $$$n-1$$$, such that $$$b_i = \max(a_i, a_{i+1})$$$ ($$$1 \le i \le n-1$$$).

For example, suppose Kristina had an array $$$a$$$ = [$$$3, 0, 4, 0, 5$$$] of length $$$5$$$. Then she did the following:

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

You only know the array $$$b$$$. Find any matching array $$$a$$$ that Kristina may have originally had.

## Input Format
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 Format
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.

## Examples
```input
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
```
```output
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$$$.

Now solve the problem and return the code.