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

Вам дана перестановка $$$a$$$ длины $$$n$$$$$$^{\text{∗}}$$$. Вы можете выполнить следующую операцию любое число раз (возможно, ноль):

  • Выберите индекс $$$1\le i\le n - 3$$$. Затем одновременно поменяйте местами $$$a_i$$$ с $$$a_{i + 2}$$$ и $$$a_{i + 1}$$$ с $$$a_{i + 3}$$$. Другими словами, перестановка $$$a$$$ будет преобразована из $$$[\ldots, a_i, a_{i+1}, a_{i+2}, a_{i+3}, \ldots]$$$ в $$$[\ldots, a_{i+2}, a_{i+3}, a_{i}, a_{i+1}, \ldots]$$$.

Определите лексикографически наименьшую перестановку$$$^{\text{†}}$$$, которую можно получить, применив вышеописанную операцию любое число раз.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Массив $$$x$$$ лексикографически меньше массива $$$y$$$ такого же размера, если и только если выполняется следующее:

  • в первой позиции, где $$$x$$$ и $$$y$$$ различны, в массиве $$$x$$$ элемент меньше, чем соответствующий элемент в $$$y$$$.
Входные данные

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4\le n\le 2\cdot 10^5$$$) — длина перестановки $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите лексикографически наименьшую перестановку, которую можно получить, применив вышеуказанную операцию любое количество раз.

Пример
Входные данные
3
4
3 4 1 2
5
5 4 3 1 2
10
10 9 8 7 6 5 4 3 2 1
Выходные данные
1 2 3 4 
2 1 3 4 5 
2 1 4 3 6 5 8 7 10 9
Примечание

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

Во втором наборе входных данных мы можем выполнить следующую последовательность операций:

  • Выполнить операцию на индексе $$$i = 2$$$. Перестановка станет $$$[5, 1, 2, 4, 3]$$$.
  • Выполнить операцию на индексе $$$i = 1$$$. Перестановка станет $$$[2, 4, 5, 1, 3]$$$.
  • Выполнить операцию на индексе $$$i = 2$$$. Перестановка станет $$$[2, 1, 3, 4, 5]$$$.