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.

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.

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