Se da una permutación $p$ de $1\sim n$.

Debes construir una secuencia $a$ de longitud $n$ que cumpla lo siguiente:

• Cada elemento de la secuencia $a$ es un entero positivo no mayor que $n$.
• No existe ningún par ordenado de enteros $(l,r)$ que cumpla $1 \le l \le r \le n$ y $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.

O bien, indica que no existe solución.

Una permutación de $1\sim n$ es una secuencia en la que cada entero positivo no mayor que $n$ aparece exactamente una vez.

Entrada

Este problema contiene varios casos de prueba.

La primera línea contiene un entero $T$, que indica el número de casos de prueba.

A continuación se dan los casos de prueba en orden. Para cada caso de prueba:

• La primera línea contiene un entero $n$.
• La segunda línea contiene $n$ enteros que representan la permutación dada $p$.

Salida

Para cada caso de prueba, imprime una línea:

• Si existe una secuencia $a$ que cumpla las condiciones, imprime $n$ enteros separados por espacios que representen la secuencia $a$ que has construido.
• Si no existe ninguna secuencia $a$ que cumpla las condiciones, imprime $-1$.

Se aceptará cualquier salida que cumpla los requisitos.

Ejemplos

Entrada 1

4
3
3 2 1
2
1 2
5
4 2 1 5 3
7
5 7 3 1 2 4 6

Salida 1

1 3 3
-1
5 3 2 1 1
2 3 5 4 6 3 1

Nota

En el caso de prueba $1$, tanto $\{1,3,3\}$ como $\{1,1,3\}$ son secuencias $a$ que cumplen las condiciones.

En el caso de prueba $2$, se puede demostrar que no existe ninguna secuencia $a$ que cumpla las condiciones.

En el caso de prueba $3$, además de $\{5,3,2,1,1 \}$, también cumplen las condiciones secuencias $a$ como $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ y $\{5,3,3,4,5\}$.

Restricciones

Sea $\sum n$ la suma de los valores de $n$ en un único archivo de prueba.

Para todos los datos, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, y se garantiza que $p$ es una permutación de $1\sim n$.