给你一个长度为 $$$n$$$$$^{\text{*}}$$$ 的排列 $$$a$$$。您可以执行以下操作任意次数(可能为零):
- 选择索引 $$$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$$$ 中的相应元素小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出通过应用上述操作任意次数可以获得的字典顺序最小排列。
示例
输入复制
343 4 1 255 4 3 1 21010 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]$$$。