Zigzag Array Sort

You are given an array of integers. Your task is to rearrange the array in a zigzag fashion in-place so that the array elements alternate between lower and higher values compared to their neighbors.

In more formal terms, for an array a of length n, you need to achieve the following conditions (using 0-based indexing):

For every index i (1 ≤ i < n):

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

Output the modified array for each test case as described in the input and output sections.

inputFormat

The input begins with an integer T, representing the number of test cases.

For each test case, the first line contains an integer n, the size of the array. The next line contains n space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing the zigzag-sorted array. The numbers should be separated by a space.

## sample

2
5
4 3 7 8 6
4
1 4 3 2

3 7 4 8 6
1 4 2 3

</p>