当前没有测试数据。

题目描述

JSB has an integer sequence $a_1, a_2, \dots, a_n$. He wants to play a game with SHB.

For each $1 \le i \le n-2$, JSB calculates the median of $\{a_i, a_{i+1}, a_{i+2}\}$, denoted by bib_ibi​. SHB is given the sequence $b_1, b_2, \dots, b_{n-2}$​. Can you help him restore the sequence $\ a$?

Recall that the median of three numbers is the second largest one of them.

输入格式

There are multiple cases. The first line of the input contains a single positive integer $\ T$, indicating the number of cases.

For each case, the first line of the input contains a single integer $n\ (3 \le n \le 10^5)$, the length of the sequence $\ a$. The second line contains $\ n-2$ integers $b_1, b_2, \dots, b_{n-2}\ (0 \le b_i \le 10^9)$.

It's guaranteed that the sum of n\ n n over all cases does not exceed $10^6$.

输出格式

For each case print one line containing $\ n$ integers, indicating the sequence $a_1, a_2, \dots, a_n$​. Your output must satisfy $0 \le a_i \le 10^9$ for each $1 \le i \le n$.

If there are multiple valid answers, you may print any of them. If there is no valid answer, print"-1" (without quotes) instead.

样例

样例输入 1

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

样例输出 1

1 1 3 2 3
1 2 1 4 3 4
1 1 4 2 4 3
-1