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$.