Wave Array Rearrangement

You are given an array of integers. Your task is to rearrange the array into a wave-like pattern such that:

[ \begin{cases} a_0 < a_1,\ a_1 > a_2,\ a_2 < a_3,\ a_3 > a_4,\ \ldots \end{cases} ]

In other words, the first element should be less than the second, the second greater than the third, the third less than the fourth, and so on. This pattern guarantees that for every valid index (i) (0-indexed):

• If (i) is odd, then (a[i] > a[i-1]).
• If (i) is even and (i > 0), then (a[i] < a[i-1]).

Print the rearranged array for each test case. It is guaranteed that an answer always exists. Note that the input array may be unsorted. One recommended method is to first sort the array and then swap adjacent elements starting from the second element.

Example:

• Input: 5\n1 3 2 4 5
• Output: 1 3 2 5 4
• Input: 3\n9 7 5
• Output: 5 9 7

inputFormat

The input begins with an integer (T) denoting the number of test cases. Each test case is described as follows:

• The first line contains an integer (n), the size of the array.
• The second line contains (n) space-separated integers representing the elements of the array.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the rearranged array in wave form. The elements must be separated by a single space. Output is written to standard output (stdout).## sample

2
5
1 3 2 4 5
3
9 7 5

1 3 2 5 4
5 9 7