Dla ciągu $s$ o długości $n$, definiujemy $p_j = x$, jeśli $s[x \dots j]$ jest najmniejszym sufiksem ciągu $s[1 \dots j]$, dla wszystkich $j = 1, \dots, n$. (Sufiks jest najmniejszym sufiksem ciągu, jeśli jest leksykograficznie mniejszy niż jakikolwiek inny sufiks tego ciągu).

Twoim zadaniem jest odtworzenie $s$ na podstawie $p_1, \dots, p_n$. Jeśli istnieje wiele rozwiązań, znajdź leksykograficznie najmniejsze z nich.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^5$) oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych, pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 3 \times 10^6$) oznaczającą długość $s$. Następna linia zawiera $n$ liczb całkowitych $p_1, \dots, p_n$ ($1 \le p_i \le i$ dla wszystkich $1 \le i \le n$).

Gwarantuje się, że suma $n$ we wszystkich zestawach danych nie przekracza $3 \times 10^6$.

Wyjście

Dla każdego zestawu danych wypisz jedną linię. Jeśli rozwiązanie nie istnieje, wypisz $-1$. W przeciwnym razie wypisz leksykograficznie najmniejszy ciąg $s$. Znaki ciągu $s$ są reprezentowane przez liczby całkowite dodatnie. Mniejsze liczby całkowite reprezentują mniejsze znaki w porządku leksykograficznym.

Przykład

Wejście 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

Wyjście 1

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

Uwagi

Ponieważ dane wejściowe/wyjściowe mogą być bardzo duże, zaleca się stosowanie szybkich metod wczytywania i wypisywania danych.