CF1339B.Sorted Adjacent Differences

You have array of $n$ numbers $a_{1}, a_{2}, \ldots, a_{n}$.

Rearrange these numbers to satisfy $|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$, where $|x|$ denotes absolute value of $x$. It's always possible to find such rearrangement.

Note that all numbers in $a$ are not necessarily different. In other words, some numbers of $a$ may be same.

You have to answer independent $t$ test cases.

你有一个包含 $n$ 个数字的数组 $a_{1}, a_{2}, \ldots, a_{n}$。

请重新排列这些数字，使其满足 $|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$，其中 $|x|$ 表示 $x$ 的绝对值。这样的重排总是存在的。

注意：数组 $a$ 中的数字不一定互不相同。换言之，$a$ 中可能存在相等的数字。

你需要独立地回答 $t$ 组测试用例。

The first line contains a single integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases.

The first line of each test case contains single integer $n$ ($3 \le n \le 10^{5}$) — the length of array $a$. It is guaranteed that the sum of values of $n$ over all test cases in the input does not exceed $10^{5}$.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($-10^{9} \le a_{i} \le 10^{9}$).

第一行包含一个整数 $t$（$1 \le t \le 10^{4}$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 10^{5}$）—— 数组 $a$ 的长度。保证输入中所有测试用例的 $n$ 值之和不超过 $10^{5}$。

每个测试用例的第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$-10^{9} \le a_{i} \le 10^{9}$）。

For each test case, print the rearranged version of array $a$ which satisfies given condition. If there are multiple valid rearrangements, print any of them.

对于每个测试用例，输出满足给定条件的数组 $a$ 的重排版本。如果存在多种有效的重排方式，输出任意一种即可。

In the first test case, after given rearrangement, $|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, $|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$. There are other possible answers like "2 4 8 1".

在第一个测试用例中，经过给定的重排后，有 $|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$。其他可能的答案还包括 “5 4 5 6 -2 8”。

在第二个测试用例中，经过给定的重排后，有 $|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$。其他可能的答案还包括 “2 4 8 1”。