J. Complete the Permutation
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an incomplete permutation of length $$$2n - 1$$$, where only odd positions are filled in with odd numbers from $$$1$$$ to $$$2n-1$$$. Complete the permutation by filling in even positions with even numbers from $$$2$$$ to $$$2n-2$$$ so that no even number is a local extremum.

A permutation of length $$$k$$$ is an array of length $$$k$$$ which contains every integer from $$$1$$$ to $$$k$$$ (inclusive) exactly once. For example, $$$p=[4, 2, 6, 5, 3, 1]$$$ is a permutation of length $$$6$$$.

An element of a permutation is a local extremum if it is either greater than both its neighbours, or less than both its neighbours.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of odd integers in the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_3, p_5, \dots, p_{2n-1}$$$ ($$$1 \le a_i \le 2n-1$$$, all $$$p_i$$$ are odd and unique) — the elements on the odd positions of the permutation.

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the answer on a separate line as follows:

  • if the answer exists, print $$$n - 1$$$ integers $$$p_2, p_4, p_6, \dots, p_{2n-2}$$$ ($$$2 \le p_i \le 2n-2$$$). All these integers should be even and unique. In the permutation $$$[p_1, p_2, \dots, p_{2n-1}]$$$, no integer on an even position should be a local extremum. In case there are multiple answers, you may print any of them;
  • otherwise, print one integer $$$-1$$$.
Example
Input
3
3
1 3 5
8
13 15 9 5 7 1 3 11
5
1 5 3 9 7
Output
2 4
14 12 8 6 4 2 10
2 4 6 8
Note

In the first test case of the example, you are given an incomplete permutation $$$[1, \_, 3, \_, 5]$$$, where underscores denote missing even numbers. The sample output provides the only valid solution for that test case: $$$[1, 2, 3, 4, 5]$$$.

The only other way to insert even numbers into the given incomplete permutation is $$$[1, 4, 3, 2, 5]$$$, and that violates the extremum requirement, as here $$$4$$$ is greater than both its neighbours $$$1$$$ and $$$3$$$.