Mystic Permutation

Description:

Input:

There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 200$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains a positive integer $$$n$$$ ($$$1\leq n\leq 1000$$$) — the length of the permutation.

The second line of each test case contains $$$n$$$ distinct positive integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). It's guaranteed that $$$p$$$ is a permutation, i. e. $$$p_i \neq p_j$$$ for all $$$i \neq j$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$1000$$$ over all test cases.

Output:

For each test case, output $$$n$$$ positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output $$$-1$$$ instead.

Sample Input:

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

Sample Output:

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

Note:

In the first test case possible permutations that are mystic are $$$[2,3,1]$$$ and $$$[3,1,2]$$$. Lexicographically smaller of the two is $$$[2,3,1]$$$.

In the second test case, $$$[1,2,3,4,5]$$$ is the lexicographically minimal permutation and it is also mystic.

In third test case possible mystic permutations are $$$[1,2,4,3]$$$, $$$[1,4,2,3]$$$, $$$[1,4,3,2]$$$, $$$[3,1,4,2]$$$, $$$[3,2,4,1]$$$, $$$[3,4,2,1]$$$, $$$[4,1,2,3]$$$, $$$[4,1,3,2]$$$ and $$$[4,3,2,1]$$$. The smallest one is $$$[1,2,4,3]$$$.