Pour une chaîne $s$ de longueur $n$, nous définissons $p_j = x$ si $s[x \dots j]$ est le suffixe minimum de $s[1 \dots j]$, pour tout $j = 1, \dots, n$. (Un suffixe est le suffixe minimum d'une chaîne s'il est lexicographiquement plus petit que tout autre suffixe de cette chaîne.)

Vous devez retrouver $s$ à partir de $p_1, \dots, p_n$. S'il existe plusieurs solutions, trouvez la plus petite lexicographiquement.

Entrée

La première ligne contient un entier unique $T$ ($1 \le T \le 10^5$) représentant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier unique $n$ ($1 \le n \le 3 \times 10^6$) représentant la longueur de $s$. La ligne suivante contient $n$ entiers $p_1, \dots, p_n$ ($1 \le p_i \le i$ pour tout $1 \le i \le n$).

Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $3 \times 10^6$.

Sortie

Pour chaque cas de test, affichez une ligne. S'il n'y a pas de solution, affichez $-1$. Sinon, affichez la chaîne $s$ la plus petite lexicographiquement. Les caractères de $s$ sont représentés par des entiers positifs. Les entiers plus petits représentent des caractères plus petits dans l'ordre lexicographique.

Exemples

Entrée 1

6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3

Sortie 1

1 2 2
-1
1 2 1
1 1 2
2 1 2
1 1 1

Remarque

Comme l'entrée/sortie peut être volumineuse, il est recommandé d'utiliser des méthodes d'entrée/sortie rapides.