Problem: You have array of n numbers a_{1}, a_{2}, …, a_{n}. 

Rearrange these numbers to satisfy |a_{1} - a_{2}| ≤ |a_{2} - a_{3}| ≤ … ≤ |a_{n-1} - a_{n}|, where |x| denotes absolute value of x. It's always possible to find such rearrangement.

Note that all numbers in a are not necessarily different. In other words, some numbers of a may be same.

You have to answer independent t test cases.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^{4}) — the number of test cases.

The first line of each test case contains single integer n (3 ≤ n ≤ 10^{5}) — the length of array a. It is guaranteed that the sum of values of n over all test cases in the input does not exceed 10^{5}.

The second line of each test case contains n integers a_{1}, a_{2}, …, a_{n} (-10^{9} ≤ a_{i} ≤ 10^{9}).

Output

For each test case, print the rearranged version of array a which satisfies given condition. If there are multiple valid rearrangements, print any of them.

Example

Input


2
6
5 -2 4 8 6 5
4
8 1 4 2


Output


5 5 4 6 8 -2
1 2 4 8

Note

In the first test case, after given rearrangement, |a_{1} - a_{2}| = 0 ≤ |a_{2} - a_{3}| = 1 ≤ |a_{3} - a_{4}| = 2 ≤ |a_{4} - a_{5}| = 2 ≤ |a_{5} - a_{6}| = 10. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, |a_{1} - a_{2}| = 1 ≤ |a_{2} - a_{3}| = 2 ≤ |a_{3} - a_{4}| = 4. There are other possible answers like "2 4 8 1".

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class Sol {
	public static StringBuffer sb = new StringBuffer();
	public static long mod = 1000000007;
	public static int t;
	public static Set<Integer> set = new HashSet<>();
	public static Map<Integer,Integer> map = new HashMap<>();
	private static long pow(long a, long b, long mod) {
		long ans = 1;
		while (b > 0) {
			if (b % 2 == 1) {
				ans = (ans * a) % mod;
			}
			a = (a * a) % mod;
			b = b >> 1;
		}
		return ans;
	}

	private static long lcm(long l, long m) {
		long gcd = Gcd(l, m);
		return (l * m) / gcd;
	}

	private static long Gcd(long a, long b) {
		if (b == 0)
			return a;
		else
			return Gcd(b, a % b);
	}

	private static int Gcd(int a, int b) {
		if (b == 0)
			return a;
		else
			return Gcd(b, a % b);
	}

	private static void solve1() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k = Integer.parseInt(str[1]);
			int b = Integer.parseInt(str[2]);
			char c = 'a';
			int j=1;
			for(int i=0;i<n;i++){
				sb.append(c);
			if(j<b){
				c++;
				j++;
			}else{
				c='a';
				j=1;
			}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
private static void solve2() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			int brr[] = new int[n];
			Arrays.sort(arr);
			int i=0,j=n-1,k=n-1;
			while(i<j){
				brr[k--]=arr[j--];
				brr[k--]=arr[i++];
			}
			if(n%2==1){
				brr[0] = arr[i];
			}
			for(int h=0;h<n;h++){
				sb.append(brr[h]+" ");
			}
			
			sb.append("\n");

		}
		System.out.println(sb);
	}
	private static void solve3() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		long arr[] = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::valueOf).toArray();
		long gcd = arr[0];
		long max = arr[0];

		for (int i = 1; i < t; i++) {
			gcd = Gcd(gcd, arr[i]);
			max = Math.max(max, arr[i]);
		}
		System.out.println(max / gcd);
	}

	

	private static void solve4() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			int n =Integer.parseInt(br.readLine());
			int max=0;
			while(n-->0){
				int j =Integer.parseInt(br.readLine());
				max=Math.max(max,j);
			}	
			sb.append(max+"\n");
		}
		System.out.println(sb);
	}

	private static void Recursion(int[] arr, int l, int r,int k) {
			if(l==r){
				arr[l]=k;
				return;
			}
			int mid=r-l+1;
			if(mid%2==1){
					arr[(r+l)/2]=k;
			} else{
				arr[(r+l+1)/2]=k;

			}
			if(arr.length%2==0){
				Recursion(arr, r/2+1, r, k+1);
				Recursion(arr, l, r/2, k+2);
			}else{
				Recursion(arr, l, r/2-1, k+1);
				Recursion(arr, r/2, r, k+2);
				
			}
	}

	private static void solve5() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k =Integer.parseInt(str[1]);
			int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			Arrays.sort(arr);
			int total=0,i=0;
			while(k>0){
				k=k-arr[i++];
				total++;
			}
			if(k<0){
				total--;
			}
			sb.append(total+"\n");
		}
		System.out.println(sb);
	}

private static void solve6() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k =Integer.parseInt(str[1]);
			long arr[] = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::valueOf).toArray();
			int query[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			long sum=arr[0];
			for(int i=1;i<n;i++){
				sum=sum^arr[i];
			}
			long brr[] = new long[n];
			brr[0] = sum;
			for(int i=1;i<n;i++){
				brr[i] = brr[i-1]^arr[i-1];
			}
			for(int i=0;i<k;i++){
				set.add(query[i]);
			}
			long max=-1;
			long count=0;
			for(int i=0;i<n;i++){
				if(set.contains(i+1)){
					max=Math.max(max,brr[i]);
				}
				if(brr[i]<max){
					count+=arr[i];
				}
			}
			sb.append(count+"\n");
		}
		System.out.println(sb);
	}
	private static long check(long n) {
		if (n == 1) {
			return 0;
		}
		long k = n/2;
		long sum=0;
		long pow=8;
		for(int i=1;i<=k;i++){
			sum+=i;
		}
		return 0;

		
	}

	public static void main(String[] args) throws IOException {
		 //solve1(); // input in the form of 
					 // 3
					 // 1 5
					 // 5 7
					 // 8 9
		 solve2(); // input in the form
					// 2
					// 3
					// 1 2 3
					// 2
					// 1 2
		// solve3();
		 //solve4();//input in the form of
				   // 3
				   // 2
				   // 6
				   // 9

		//solve5();
		//solve6();

	}

	private static void solve() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int t = Integer.parseInt(br.readLine());
		int left=0,right=1,totalleft=0;
		while (t-- > 0) {
			System.out.println();
			int k=-1,pos=0;
			for(int i=0;i<9;i++){
				if(i%3==0){
					k++;	
					pos=k;
				}
				char[] s = br.readLine().toCharArray();
				if(s[pos]=='1'){
					s[pos]='2';
				}else
				s[pos]='1';
				pos+=3;
				sb.append(String.valueOf(s)+"\n");
			}
			
		}System.out.println(sb);
	}
}