Para una cadena $s$ de longitud $n$, definimos $p_j = x$ si $s[x \dots j]$ es el sufijo mínimo de $s[1 \dots j]$, para todo $j = 1, \dots, n$. (Un sufijo es el sufijo mínimo de una cadena si es lexicográficamente menor que cualquier otro sufijo de esa cadena).

Debes recuperar $s$ a partir de $p_1, \dots, p_n$. Si existen múltiples respuestas, encuentra la lexicográficamente más pequeña.

Entrada

La primera línea contiene un único entero $T$ ($1 \le T \le 10^5$) que representa el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un único entero $n$ ($1 \le n \le 3 \times 10^6$) que representa la longitud de $s$. La siguiente línea contiene $n$ enteros $p_1, \dots, p_n$ ($1 \le p_i \le i$ para todo $1 \le i \le n$).

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $3 \times 10^6$.

Salida

Para cada caso de prueba, imprime una línea. Si no hay solución, imprime $-1$. De lo contrario, imprime la cadena $s$ lexicográficamente más pequeña. Los caracteres de $s$ están representados por enteros positivos. Los enteros más pequeños representan caracteres más pequeños en el orden lexicográfico.

Ejemplos

Entrada 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

Salida 1

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

Nota

Dado que la entrada/salida puede ser muy grande, se recomienda utilizar métodos de entrada/salida rápidos.