Problem8396--CodeChef ANUUND - Ups and Downs

8396: CodeChef ANUUND - Ups and Downs

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB  Special Judge

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

You will be given a zero-indexed array A. You need to rearrange its elements in such a way that the following conditions are satisfied:
  • A[i] ≤ A[i+1] if i is even.
  • A[i] ≥ A[i+1] if i is odd.
In other words the following inequality should hold: A[0] ≤ A[1] ≥ A[2] ≤ A[3] ≥ A[4], and so on. Operations ≤ and ≥ should alter.

Input

The first line contains a single integer T denoting the number of test cases. 
The first line of each test case contains an integer N, that is the size of the array A. 
The second line of each test case contains the elements of array A

Output

For each test case, output a single line containing N space separated integers, which are the elements of A arranged in the required order. 
If there are more than one valid arrangements, you can output any of them.

Constraints

1 ≤ N ≤ 100,000
Sum of N in one test file ≤ 600000
1 ≤ A[i] ≤ $10^9$

Sample 1 Input 

2
2
3 2
3
10 5 2

Sample 1 Output 

2 3
2 10 5

Sample 2 Input 

2
2
3 2
3
10 5 2

Sample 2 Output 

2 3
5 10 2

HINT

相同题目：CodeChef ANUUND。

Source/Category

 
Submit