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:
	/*	/ ﾌﾌ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ム
		/ )\⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀  Y
		(⠀⠀| ( ͡° ͜ʖ ͡°）⠀⌒(⠀ ノ
		(⠀ ﾉ⌒ Y ⌒ヽ-く __／
		| _⠀｡ノ| ノ｡ |/
		(⠀ー '_人`ー ﾉ
		⠀|\ ￣ _人'彡ﾉ
		⠀ )\⠀⠀ ｡⠀⠀ /
		⠀⠀(\⠀ #⠀ /
		⠀/⠀⠀⠀/ὣ====================D-
		/⠀⠀⠀/⠀ \ \⠀⠀\
		( (⠀)⠀⠀⠀⠀ ) ).⠀)
		(⠀⠀)⠀⠀⠀⠀⠀( | /
		|⠀ /⠀⠀⠀⠀⠀⠀ | /
		[_] ⠀⠀⠀⠀⠀[___]                     */
	// Main Code at the Bottom
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	import java.math.BigInteger; 
	public class Main {
		//Fast IO class
	    static class FastReader {
	        BufferedReader br; 
	        StringTokenizer st; 
	        public FastReader() {
	        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
	        	if(!env) {
	        		try {
						br=new BufferedReader(new FileReader("src\\input.txt"));
					} catch (FileNotFoundException e) {
						e.printStackTrace();
					}
	        	}
	        	else br = new BufferedReader(new InputStreamReader(System.in)); 
	        } 
	        String next() {
	            while (st == null || !st.hasMoreElements()) {
	                try {
	                    st = new StringTokenizer(br.readLine()); 
	                } 
	                catch (IOException  e) {
	                    e.printStackTrace(); 
	                } 
	            } 
	            return st.nextToken(); 
	        } 
	        int nextInt() {
	            return Integer.parseInt(next()); 
	        } 
	        long nextLong() {
	            return Long.parseLong(next()); 
	        } 
	        double nextDouble() {
	            return Double.parseDouble(next()); 
	        } 
	        String nextLine() {
	            String str = ""; 
	            try {
	                str = br.readLine(); 
	            } 
	            catch (IOException e) {
	                e.printStackTrace(); 
	            } 
	            return str; 
	        } 
	    }     
	    static long MOD=1000000000+7;
	    //Euclidean Algorithm
	    static long gcd(long A,long B){
	    	return (B==0)?A:gcd(B,A%B);
	    }
	    //Modular Exponentiation
	    static long fastExpo(long x,long n){
	        if(n==0) return 1;
	        if((n&1)==0) return fastExpo((x*x)%MOD,n/2)%MOD;
	        return ((x%MOD)*fastExpo((x*x)%MOD,(n-1)/2))%MOD;
	    }
	    //Modular Inverse
	    static long inverse(long x) {
	    	return fastExpo(x,MOD-2);
	    }
	    //Prime Number Algorithm
	    static boolean isPrime(long n){
	        if(n<=1) return false;
	        if(n<=3) return true;
	        if(n%2==0 || n%3==0) return false;
	        for(int i=5;i*i<=n;i+=6) if(n%i==0 || n%(i+2)==0) return false;
	        return true;
	    }
	    //Reverse an array
	    static void reverse(int arr[],int l,int r){
	    	while(l<r) {
	    		int tmp=arr[l];
	    		arr[l++]=arr[r];
	    		arr[r--]=tmp;
	    	}
	    }
	    //Print array
	    static void print1d(int arr[]) {
	    	out.println(Arrays.toString(arr));
	    }
	    static void print2d(int arr[][]) {
	    	for(int a[]: arr) out.println(Arrays.toString(a));
	    }
	    // Pair
	    static class pair{
	    	int x,y;
	    	pair(int a,int b){
	    		this.x=a;
	    		this.y=b;
	    	}
	    	public boolean equals(Object obj) {
	    		if(obj == null || obj.getClass()!= this.getClass()) return false;
	            pair p = (pair) obj;
	            return (this.x==p.x && this.y==p.y);
	        }
	    	public int hashCode() {
	            return Objects.hash(x,y);
	        }
	    }
	    static FastReader sc=new FastReader();
	    static PrintWriter out=new PrintWriter(System.out);  
	    //Main function(The main code starts from here
	    public static void main (String[] args) throws java.lang.Exception {
	    	int test;
	    	test=1;
	    	test=sc.nextInt();
	    	while(test-->0){
	    		int n=sc.nextInt();
	    		Long a[]=new Long[n];
	    		ArrayList<Long> ans=new ArrayList<>();
	    		for(int i=0;i<n;i++) a[i]=sc.nextLong();
	    		Arrays.sort(a);
	    		if(n%2==1) ans.add(a[n/2]);
	    		for(int i=n/2-1;i>=0;i--) {
    				ans.add(a[i]);
    				ans.add(a[n-i-1]);
    			}
	    		for(Long x: ans) out.print(x+" ");
	    		out.println();
	    	}
	        out.flush();
	        out.close();
	    }
	}