É dada uma permutação $p$ de $1\sim n$.

Você deve construir uma sequência $a$ de comprimento $n$ que satisfaça:

• Cada elemento da sequência $a$ é um inteiro positivo não superior a $n$.
• Não existe nenhum par ordenado de inteiros $(l,r)$ que satisfaça $1 \le l \le r \le n$ e $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.

Ou informe que não existe solução.

Uma permutação de $1\sim n$ é uma sequência em que cada inteiro positivo não superior a $n$ aparece exatamente uma vez.

Entrada

Este problema contém vários casos de teste.

A primeira linha contém um inteiro $T$, que indica o número de casos de teste.

Em seguida, são fornecidos os casos de teste em ordem. Para cada caso de teste:

• A primeira linha contém um inteiro $n$.
• A segunda linha contém $n$ inteiros que representam a permutação dada $p$.

Saída

Para cada caso de teste, imprima uma linha:

• Se existir uma sequência $a$ que satisfaça as condições, imprima $n$ inteiros separados por espaços que representem a sequência $a$ construída.
• Se não existir uma sequência $a$ que satisfaça as condições, imprima $-1$.

Qualquer saída que satisfaça os requisitos será aceita.

Exemplos

Entrada 1

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

Saída 1

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

Nota

No caso de teste $1$, tanto $\{1,3,3\}$ como $\{1,1,3\}$ são sequências $a$ que satisfazem as condições.

No caso de teste $2$, pode-se provar que não existe uma sequência $a$ que satisfaça as condições.

No caso de teste $3$, além de $\{5,3,2,1,1 \}$, sequências $a$ como $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ e $\{5,3,3,4,5\}$ também satisfazem as condições.

Restrições

Seja $\sum n$ a soma dos valores de $n$ em um único arquivo de teste.

Para todos os dados, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, e é garantido que $p$ é uma permutação de $1\sim n$.