CF1526A.Mean Inequality

You are given an array $a$ of $2n$ distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its $2$ neighbours.

More formally, find an array $b$, such that:

• $b$ is a permutation of $a$.

• For every $i$ from $1$ to $2n$, $b_i \neq \frac{b_{i-1}+b_{i+1}}{2}$, where $b_0 = b_{2n}$ and $b_{2n+1} = b_1$.

It can be proved that under the constraints of this problem, such array $b$ always exists.

给你一个包含 $2n$ 个互不相同整数的数组 $a$。你需要将该数组的元素排成一个环形，使得任意一个元素都不等于其两个相邻元素的算术平均值。

更准确地说，请找出一个数组 $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$ 总是存在的。

The first line of input contains a single integer $t$ $(1 \leq t \leq 1000)$ — the number of testcases. The description of testcases follows.

The first line of each testcase contains a single integer $n$ $(1 \leq n \leq 25)$.

The second line of each testcase contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ $(1 \leq a_i \leq 10^9)$ — elements of the array.

Note that there is no limit to the sum of $n$ over all testcases.

输入的第一行包含一个整数 $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$ 值之和没有限制。

For each testcase, you should output $2n$ integers, $b_1, b_2, \ldots b_{2n}$, for which the conditions from the statement are satisfied.

对于每个测试用例，你应该输出 $2n$ 个整数 $b_1, b_2, \ldots, b_{2n}$，使得题目陈述中的条件得到满足。

In the first testcase, array $[3, 1, 4, 2, 5, 6]$ works, as it's a permutation of $[1, 2, 3, 4, 5, 6]$, and $\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$.

在第一个测试用例中，数组 $[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$。