You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Sorted Adjacent Differences

题面翻译

题意简述

给定一个由$n(1\le n\le 10^{5})$个整数$a_{1},a_{2},a_{3}…a_{n}$组成的数组，请你给出任意一种排列方式使得排列后的数组满足$\left|a_{1}-a_{2}\right|\le\left|a_{2}-a_{3}\right|…\le\left| a_{n-1}-a_{n}\right|$，其中$\left|x\right|$表示$x$的绝对值。

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

输入格式

第一行包含一个正整数$t$，表示测试用例的数量。

接下来$t$组测试用例，对于每一组测试用例：

第一行包含一个正整数$n$，意义同上。

第二行包含$n$个整数，为给定的数组。

输出格式

对于每一组测试用例，输出任意一种满足条件的排列方式。

题目描述

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.

输入格式

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}$ ).

输出格式

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.

样例 #1

样例输入 #1

2
6
5 -2 4 8 6 5
4
8 1 4 2

样例输出 #1

5 5 4 6 8 -2
1 2 4 8

提示

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".