E. Enemies of the heir... beware
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Harry was in detention when he started to hear a strange voice. He went out and kept following the voice until he found a message written in blood on the wall. The message said "The Chamber of Secrets has been opened, enemies of the heir... beware". There was also a sequence of N integers. Harry looked into the mystery and found out that there is a secret room where a giant Basilisk is living. However, he couldn't understand the written numbers. Fortunately, Moaning Myrtle was passing by. She told him that the sequence of numbers on the wall is a prefix function used to open the door to the chamber. In fact, any sequence of numbers that has the given prefix function will open the door.

The prefix function of an array $$$a$$$ of size $$$n$$$ is a sequence $$$P_{1},P_{2}...P_{n}$$$, where $$$P_{i}$$$ is the maximum value of $$$k$$$ such that $$$k \lt i$$$ and $$$A[1..k] = A[i-k+1..i]$$$ ($$$A[l..r]$$$ denotes a sub-array of an array $$$A$$$ from a position $$$l$$$ to a position $$$r$$$, inclusive). In other words, it's the longest proper prefix of the string $$$A[1..i]$$$ that is equal to its suffix of the same length. Note that the empty array is both a common prefix and suffix of all arrays. Finally, $$$A[i..j]$$$ is the empty array if $$$i \gt j$$$.

For example, for the array $$$A = [1,2,1,3,1,2,1]$$$, the values of the prefix function in positions $$$1,2,...,7$$$ are equal to $$$P=[0,0,1,0,1,2,3]$$$.

Help Harry find a valid sequence of numbers.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$1 \le T \le 10^4$$$. Description of the test cases follows.

The first line of each test case contains a single number $$$1 \le n \le 10^{5}:$$$ The length of the array $$$P$$$.

The second line of each test case contains $$$n$$$ integers $$$0\le P_{1},P_{2}, \dots, P_{n} \le n$$$.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2\times 10^{5}$$$.

Output

If such an array exists, output $$$n$$$ integers $$$0 \le A_{1},\dots,A_n \le n$$$. Otherwise, output $$$-1$$$.

Example
Input
4
7
0 0 1 0 1 2 3
6
0 1 0 1 2 1
6
0 1 2 3 4 1
8
0 1 0 1 2 2 3 0
Output
1 2 1 3 1 2 1 
-1
-1
1 1 2 1 1 1 2 3