题目描述

给定一个长度为 $n$ 的排列 $a$ $^{\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$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（因为 $2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

$^{\text{†}}$ 对于两个相同长度的数组 $x$ 和 $y$，$x$ 字典序小于 $y$ 当且仅当满足以下条件：

• 在第一个 $x$ 和 $y$ 不同的位置，$x$ 的元素小于 $y$ 的对应元素。

输入格式

输入自文件$swap.in$。

多组数据，第一行一个整数 $t(1\le t\le 1000)$。

对于每组数据，第一行一个整数 $n(4\le n\le 2\times 10^5)$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le n)$，保证 $a$ 为 $1$ 到 $n$ 的排列。

保证所有测试点的 $n$ 之和不超过 $2\times 10^5$。

输出格式

输出至文件$swap.out$。

对于每组数据，输出一行 $n$ 个整数，表示可以得到的字典序最小的排列。

输入输出样例 #1

输入 #1

3
4
3 4 1 2
5
5 4 3 1 2
10
10 9 8 7 6 5 4 3 2 1

输出 #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]$。

时间限制： 2s

空间限制： 256MB