F. Tyger Sort
time limit per test
2.5 s
memory limit per test
128 MB
input
standard input
output
standard output

Tyger has a permutation $$$p_1, p_2, ..., p_n$$$ of size $$$n$$$, and he wants to sort it with his newly invented algorithm — Tyger Sort. The pseudocode of the process of Tyger sort follows: 

for x from n to 1
    i = 1
    
    while p[i] != x
        i := i + 1
        
    while i > 1 and p[i] < p[i - 1]
        swap(p[i], p[i - 1])
        i := i - 1
Unfortunately though, this sorting algorithm doesn't always work. For example, after applying Tyger sort to the permutation $$$[3, 1, 2]$$$, the result is $$$[1, 3, 2]$$$ instead of the desired $$$[1, 2, 3]$$$ because $$$2$$$ never gets swapped before $$$3$$$. But since Tyger still loves his algorithm, he decides to play a game with you.

You are given a permutation $$$a_1, a_2, ..., a_n$$$ of size $$$n$$$. Your task is to construct a permutation $$$p_1, p_2, ..., p_n$$$ so that the resulting permutation after applying Tyger sort on $$$p$$$ is $$$a$$$, or output $$$-1$$$ if no such permutation exists.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, representing the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ – denoting the permutation $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \times 10^5$$$.

Output

For each testcase, output a permutation $$$p_1, p_2, ..., p_n$$$ so that it results in $$$a_1, a_2, ..., a_n$$$ after applying Tyger sort, or $$$-1$$$ if no such permutation exists. If multiple solutions exist, output any.

Example
Input
3
5
1 2 3 4 5
3
1 3 2
4
4 3 2 1
Output
1 2 3 4 5
3 1 2
-1
Note

For the first testcase, since no swaps are performed, 1 2 3 4 5 remains as 1 2 3 4 5. For the third testcase, it can be proven that the given permutation can't be a result of Tyger-Sorting a permutation.

Credit: C0DET1GER