Rearrange Array into Peak Pattern

You are given an array of n integers. Your task is to rearrange the array such that every element at an odd index (i.e. the 2nd, 4th, etc. elements, considering 0-based indexing) is greater than its immediate neighbors.

More formally, for every odd index i (with 1 \le i \le n-2), the condition \[ a_{i} > a_{i-1} \quad \text{and} \quad a_{i} > a_{i+1} \] must hold. If the array has only one or two elements, simply output the sorted order. It is guaranteed that a valid rearrangement exists for the given input.

Note: The answer is not necessarily unique. Any valid rearrangement will be accepted.

inputFormat

The input is given via standard input and is formatted as follows:

T
N1
a11 a12 ... a1N1
N2
a21 a22 ... a2N2
... 
NT
aT1 aT2 ... aTNT

Where:

• T is the number of test cases.
• For each test case, Ni denotes the number of elements in the array, followed by a line containing Ni space-separated integers.

outputFormat

For each test case, output a single line containing the rearranged array. The elements should be space-separated. The rearranged array must satisfy the peak condition for indices 1, 3, 5, ... (if applicable).

## sample

3
5
1 3 2 4 5
4
1 2 3 4
3
2 1 3

1 3 2 5 4
1 3 2 4
1 3 2

</p>