Дана перестановка $p$ чисел $1\sim n$.

Нужно построить последовательность $a$ длины $n$, удовлетворяющую следующим условиям:

• Каждый элемент последовательности $a$ — положительное целое число, не превосходящее $n$.
• Не существует упорядоченной пары целых чисел $(l,r)$, для которой $1 \le l \le r \le n$ и $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.

Либо сообщите, что решения нет.

Здесь перестановкой чисел $1\sim n$ называется последовательность, в которой каждое положительное целое число, не превосходящее $n$, встречается ровно один раз.

Входные данные

В задаче несколько наборов входных данных.

Первая строка содержит целое число $T$ — количество наборов входных данных.

Далее по порядку следуют наборы входных данных. Для каждого набора:

• Первая строка содержит целое число $n$.
• Вторая строка содержит $n$ целых чисел, задающих данную перестановку $p$.

Выходные данные

Для каждого набора данных выведите одну строку:

• Если существует последовательность $a$, удовлетворяющая условиям, выведите $n$ целых чисел через пробел, задающих построенную вами последовательность $a$.
• Если последовательности $a$, удовлетворяющей условиям, не существует, выведите $-1$.

Будет принят любой вывод, удовлетворяющий требованиям.

Примеры

Входные данные 1

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

Выходные данные 1

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

Примечание

В наборе данных $1$ обе последовательности $\{1,3,3\}$ и $\{1,1,3\}$ являются последовательностями $a$, удовлетворяющими условиям.

Для набора данных $2$ можно доказать, что последовательности $a$, удовлетворяющей условиям, не существует.

В наборе данных $3$, помимо $\{5,3,2,1,1 \}$, условиям удовлетворяют и такие последовательности $a$, как $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ и $\{5,3,3,4,5\}$.

Ограничения

Пусть $\sum n$ обозначает сумму значений $n$ в одном тестовом файле.

Для всех данных $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$; гарантируется, что $p$ — перестановка чисел $1\sim n$.