find hidden array

Problem Description

You are given an integer $N$. There is a hidden array of size $2 \times N$ containing a permutation of $1 \sim 2 \times N$. There is an empty set. Initially, the first $N$ integers of this array are inserted into the set. Then, there are $N$ operations performed. The $i$-th operation is one of the following two actions:

1. take out the LARGEST number from the set, and then insert the $(i+N)$-th number from the array into the set.
2. take out the SMALLEST number from the set, and then insert the $(i+N)$-th number from the array into the set. For each operation, you only know which action is taken and what's the number taken out from the set. Please find out the content of the hidden array based on the given information. If there are many possible such arrays, you must output the lexicographically smallest one.

Input

The first line contains an integer $T$ indicating there are $T$ tests. Each test consists of two lines. the first line contains one positive integer $N$ indicating that the size of the hidden array is $2 \times N$. The second line contains $N$ integers $b_1, b_2, \ldots, b_N$ describe the operations. For the $i$-th operation, the LARGEST number with value $b_i$ is taken out from the set if $b_i$ is positive; Otherwise, $b_i$ is negative which means the SMALLEST number with value $-b_i$ is taken out from the set in the $i$-th operation.

• $1 \le T \le 5 \times 10^5$
• $1 \le N \le 5 \times 10^4$
• sum of all $N$ across tests $\le 5 \times 10^5$
• $-2 \times N \le b_i \le 2 \times N$
• $|b_i|$ are all distinct in a test

Output

For each test, if it's impossible to recover such array, output a single integer $-1$ in a line. Otherwise, output $2 \times N$ positive integers, indicating the array you recovered. If there are multiple ways, you should choose the lexicographically smallest one.

Sample Input

4

3

-1 4 -2

1

2

2

-4 3

4

-2 8 6 -3

Sample Output

1 2 3 4 5 6

2 1

-1

2 3 4 5 8 6 7 1

Source

2019 Multi-University Training Contest 5