B. 四元组交换

每个测试的时间限制：2 秒
内存限制：256 MB

给你一个长度为 $n$ 的排列 $a$。你可以进行任意多次（包括零次）如下操作：

• 选择一个下标 $1 \le i \le n-3$，然后同时交换 $a_i$ 与 $a_{i+2}$，以及 $a_{i+1}$ 与 $a_{i+3}$。
  换句话说，排列 $a$ 将变为：$$[\dots, a_i, a_{i+1}, a_{i+2}, a_{i+3}, \dots] \to [\dots, a_{i+2}, a_{i+3}, a_i, a_{i+1}, \dots] $$

请确定通过任意次上述操作可以得到的字典序最小的排列。

定义

• 一个长度为 $n$ 的排列是由 $n$ 个不同的整数 $1$ 到 $n$ 按任意顺序组成的数组。
  例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 却出现了 $4$）。

• 对于两个长度相同的数组 $x$ 和 $y$，称 $x$ 字典序小于 $y$，当且仅当在它们第一个不同的位置上，$x$ 中的元素小于 $y$ 中的对应元素。

输入
每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数。
每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 2 \cdot 10^5$），表示排列的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, 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]$，这是字典序最小的可达排列。
• 第二个测试用例：可以通过以下操作序列得到 $[2,1,3,4,5]$：
  1. 对 $i=2$ 操作：$[5,4,3,1,2] \to [5,1,2,4,3]$
  2. 对 $i=1$ 操作：$[5,1,2,4,3] \to [2,4,5,1,3]$
  3. 对 $i=2$ 操作：$[2,4,5,1,3] \to [2,1,3,4,5]$