Дано перестановку $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$.