C. Range Contradiction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a(a_{1},a_{2},....,a_{n})$$$containing $$$n$$$ elements, it is guaranteed that $$$n$$$ is even.

Let's define some definitions:

  • $$$S_{1}(a)$$$ is defined as set of elements in $$$a$$$ at odd index positions. i.e., $$$S_{1}(a) = (a_{1},a_{3},....,a_{n-1})$$$.
  • $$$S_{2}(a)$$$ is defined as set of elements in $$$a$$$ at even index positions. i.e., $$$S_{2}(a) = (a_{2},a_{4},....,a_{n})$$$.
  • $$$R(S)$$$ is defined as the Range$$$^\dagger$$$ of the set $$$S$$$.
  • $$$f(a) = R(S_{1}(a))*R(S_{2}(a))$$$

You are allowed to do the following operation on $$$a$$$:

  • Choose $$$i,j(1 \le i,j \le n)$$$ and swap $$$a_{i}$$$ and $$$a_{j}$$$.

Let the array $$$b$$$ be the resultant array $$$a$$$ after performing above operation any times(possibly zero).

Output any $$$b$$$ which has minimum $$$f(b)$$$.

$$$^\dagger$$$ Range of the set $$$S$$$ is defined as the difference between the maximum element and minimum element in $$$S$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of test case contains a single integers $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$, it is guaranteed thar $$$n$$$ is even.

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

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print $$$n$$$ space seperated integers — the array $$$b$$$ which has minimum $$$f(b)$$$.

Example
Input
5
2
1 2
4
3 9 7 5
4
2 4 4 4
6
3 2 1 6 5 4
6
1000 1000 1000 1000 1000 1000
Output
2 1
9 5 7 3
2 4 4 4
3 5 1 6 2 4
1000 1000 1000 1000 1000 1000
Note

In the $$$4^{th}$$$ test case,

Let $$$b = (3,5,1,6,2,4)$$$

So, $$$S_{1}(b) = (3,1,2)$$$ and $$$S_{2}(b) = (5,6,4)$$$

so, $$$R(S_{1}(b)) = (3 - 1) = 2$$$ and $$$R(S_{2}(b)) = (6 - 4) = 2$$$

Hence, $$$f(b) = 2 * 2 = 4$$$.

It is shown that, there is no other $$$b$$$ where $$$f(b)$$$ is smaller than $$$4$$$.