给你一个数组 $$$a$$$,其中包含 $$$2n$$$ 不同的整数。您希望将数组的元素排列在一个圆圈中,使得没有元素等于其 $$$2$$$ 邻居的算术平均值。
更正式地说,找到一个数组 $$$b$$$,这样:
- $$$b$$$ 是 $$$a$$$ 的排列。
- 对于从 $$$1$$$ 到 $$$2n$$$ 的每个 $$$i$$$,$$$b_i \neq \frac{b_{i-1}+b_{i+1}}{2}$$$,其中 $$$b_0 = b_{2n}$$$ 且 $$$b_{2n+1} = b_1$$$。
可以证明,在本问题的约束下,这样的数组$$$b$$$总是存在的。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 25)$$$。
每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ $$$(1 \leq a_i \leq 10^9)$$$ — 数组的元素。
请注意,所有测试用例的 $$$n$$$ 总和没有限制。
输出
对于每个测试用例,您应该输出 $$$2n$$$ 整数,$$$b_1, b_2, \ldots b_{2n}$$$,满足语句中的条件。
示例
输入 #1
3 3 1 2 3 4 5 6 2 123 456 789 10 1 6 9
输出 #1
3 1 4 2 5 6 123 10 456 789 9 6
注意
在第一个测试用例中,数组 $$$[3, 1, 4, 2, 5, 6]$$$ 有效,因为它是 $$$[1, 2, 3, 4, 5, 6]$$$ 和 $$$\frac{3+4}{2}\neq 1$$$, $$$\frac{1+2}{2}\neq 的排列4$$$、$$$\frac{4+5}{2}\neq 2$$$、$$$\frac{2+6}{2}\neq 5$$$、$$$\frac{5+3}{2}\neq 6$$$、$$$\frac{6+1}{2}\neq 3$$$。