You are given an integer NN. There is a hidden array of size 2×N2×N containing a permutation of 1∼2×N1∼2×N.
There is an empty set. Initially, the first NN integers of this array are inserted into the set. Then, there are NN operations performed. The ii-th operation is one of the following two actions:
1. take out the LARGEST number from the set, and then insert the (i+N)(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)(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 TT indicating there are TT tests.
Each test consists of two lines. the first line contains one positive integer NNindicating that the size of the hidden array is 2×N2×N. The second line contains NNintegers b1,b2,…,bNb1,b2,…,bN describe the operations. For the ii-th operation, the LARGEST number with value bibi is taken out from the set if bibi is positive; Otherwise, bibi is negative which means the SMALLEST number with value −bi−bi is taken out from the set in the ii-th operation.
* 1≤T≤5×1051≤T≤5×105
* 1≤N≤5×1041≤N≤5×104
* sum of all NN across tests ≤5×105≤5×105
* −2×N≤bi≤2×N−2×N≤bi≤2×N
* |bi||bi| are all distinct in a test
Output
For each test, if it's impossible to recover such array, output a single integer −1−1in a line. Otherwise, output 2×N2×N positive integers, indicating the array you recovered. If there are multiple ways, you should choose the lexicographically smallest one.