B. Странная перестановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп — маленький мальчик, который живет в Байтландии и любит программировать.

Недавно он нашел перестановку длины $$$n$$$. Он должен придумать странную перестановку. Это должна быть новая перестановка, отличающаяся от старой в каждой позиции.

Более формально, если старая перестановка равна $$$p_1,p_2,\ldots,p_n$$$, а новая — $$$q_1,q_2,\ldots,q_n$$$, то должно выполняться $$$$$$p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.$$$$$$

Монокарп боится лексикографически больших перестановок. Не могли бы вы помочь ему найти лексикографически минимальную странную перестановку?

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\leq t\leq 200$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1\leq n\leq 1000$$$) — длина перестановки.

Во второй строке каждого набора задано $$$n$$$ различных положительных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). Гарантируется, что $$$p$$$ является перестановкой, т. е. $$$p_i \neq p_j$$$ для всех $$$i \neq j$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых положительных чисел — лексикографически минимальную странную перестановку. Если такой перестановки не существует, выведите вместо нее $$$-1$$$.

Пример
Входные данные
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
Выходные данные
2 3 1
1 2 3 4 5
1 2 4 3
-1
Примечание

В первом наборе входных данных всевозможными странными перестановками являются $$$[2,3,1]$$$ и $$$[3,1,2]$$$. Лексикографически меньшая из них равна $$$[2,3,1]$$$.

Во втором наборе входных данных $$$[1,2,3,4,5]$$$  — это лексикографически минимально возможная перестановка, и она является странной.

В третьем наборе входных данных возможные странные перестановки: $$$[1,2,4,3]$$$, $$$[1,4,2,3]$$$, $$$[1,4,3,2]$$$, $$$[3,1,4,2]$$$, $$$[3,2,4,1]$$$, $$$[3,4,2,1]$$$, $$$[4,1,2,3]$$$, $$$[4,1,3,2]$$$ и $$$[4,3,2,1]$$$. Минимальная из них  — $$$[1,2,4,3]$$$.