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 TP {

    public static PrintWriter out;
    public static FastReader in;


    public static void main(String[] args) throws IOException {
        long s = System.currentTimeMillis();
        in = new FastReader();
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new BufferedWriter(new FileWriter("whereami.out")));
        int t = 1;
        t = ni();
        while (t-- > 0) solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");
    }


    private static void solve() {
        int n = ni();
        int[] a = na(n);
        Arrays.sort(a);
        int[] d = new int[n];
        int index = n - 1;
        for (int i = 0; i < n / 2; i++) {
            d[index] = a[n - i - 1];
            index--;
            d[index] = a[i];
            index--;
        }
        if (n % 2 != 0) {
            d[index] = a[n / 2];
        }
        for (int x : d) System.out.print(x + " ");
        System.out.println();
    }

    private static boolean check(long mid, long n, long d) {
        long h = (long) Math.ceil(d * 1d / (mid + 1));
        return (mid + h) <= n;
    }

    private static boolean sorted(char[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) return false;
        }
        return true;
    }


    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    public static int[][] enumPrimesAndLPF(int n) {
        int[] lpf = new int[n + 1];
        double lu = Math.log(n + 32);

        int tot = 0;
        int[] primes = new int[(int) ((n + 32) / lu + (n + 32) / lu / lu * 1.5)];

        for (int i = 2; i <= n; i++) {
            lpf[i] = i;
        }

        for (int p = 2, tmp; p <= n; p++) {
            if (lpf[p] == p) {
                primes[tot++] = p;
            }
            for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
                lpf[tmp] = primes[i];
            }
        }

        return new int[][]{Arrays.copyOf(primes, tot), lpf};
    }

    static boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    static boolean sorted(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) return false;
        }
        return true;
    }

    public static long gcd(long a, long b) {
        while (b != 0) {
            a %= b;
            long t = a;
            a = b;
            b = t;
        }
        return a;
    }

    private static int ni() {
        return in.nextInt();
    }

    private static String ns() {
        return in.next();
    }

    private static int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private static long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private static long nl() {
        return in.nextLong();
    }

    private float nf() {
        return (float) in.nextDouble();
    }

    private static double nd() {
        return in.nextDouble();
    }

    public static int[] facs(int n, int[] primes) {
        int[] ret = new int[9];
        int rp = 0;
        for (int p : primes) {
            if (p * p > n) break;
            int i;
            i = 0;
            while (n % p == 0) {
                n /= p;
                i++;
            }
            if (i > 0) ret[rp++] = p;
        }
        if (n != 1) ret[rp++] = n;
        return Arrays.copyOf(ret, rp);
    }

    public static int[] sieveEratosthenes(int n) {
        if (n <= 32) {
            int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
            for (int i = 0; i < primes.length; i++) {
                if (n < primes[i]) {
                    return Arrays.copyOf(primes, i);
                }
            }
            return primes;
        }

        int u = n + 32;
        double lu = Math.log(u);
        int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
        ret[0] = 2;
        int pos = 1;

        int[] isnp = new int[(n + 1) / 32 / 2 + 1];
        int sup = (n + 1) / 32 / 2 + 1;

        int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int tp : tprimes) {
            ret[pos++] = tp;
            int[] ptn = new int[tp];
            for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31);
            for (int j = 0; j < sup; j += tp) {
                for (int i = 0; i < tp && i + j < sup; i++) {
                    isnp[j + i] |= ptn[i];
                }
            }
        }

        // 3,5,7
        // 2x+3=n
        int[] magic = {
                0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21,
                17, 9, 6, 16, 5, 15, 14
        };
        int h = n / 2;
        for (int i = 0; i < sup; i++) {
            for (int j = ~isnp[i]; j != 0; j &= j - 1) {
                int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
                int p = 2 * pp + 3;
                if (p > n) break;
                ret[pos++] = p;
                if ((long) p * p > n) continue;
                for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q;
            }
        }

        return Arrays.copyOf(ret, pos);
    }


    private static final boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private static void tr(Object... o) {
        if (!oj) System.out.println(Arrays.deepToString(o));
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() throws FileNotFoundException {
            br = new BufferedReader(new InputStreamReader(System.in));
//            br = new BufferedReader(new FileReader("whereami.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());
        }
    }

    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public void setValue(V value) {
            this.value = value;
        }

    }
}