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:
//package com.prituladima.b;


import java.io.*;
import java.util.*;

import static java.lang.Double.parseDouble;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.util.Arrays.stream;
import static java.util.stream.IntStream.range;

public final class Main {

    private void solve(int testNumber) {
        int n = nextInt();
        long[] a = nextArrL(n);
        safeSort(a);
        List<Long> ans = new ArrayList<>();
        int i = 0, j = n - 1;
        for (; i < j; i++, j--) {
            ans.add(a[j]);
            ans.add(a[i]);
        }
        if(i == j){
            ans.add(a[j]);
        }
        Collections.reverse(ans);
        
        for (long b: ans)
            print(b + " ");
        println();
    }

    public static void safeSort(long[] array) {
        shuffle(array);
        Arrays.sort(array);
    }

    public static void shuffle(long[] array) {
        Random random = new Random();
        for (int i = 0, j; i < array.length; i++) {
            j = i + random.nextInt(array.length - i);
            long buf = array[j];
            array[j] = array[i];
            array[i] = buf;
        }
    }

    private void solve() {
        int t = nextInt();
        while (t-- > 0) {
            solve(t);
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }

    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter writer;

    private void run() {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
             PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out))) {
            this.reader = reader;
            this.writer = writer;
            this.tokenizer = null;
            solve();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }


    private int nextInt(int radix) {
        return parseInt(nextToken(), radix);
    }

    private int nextInt() {
        return parseInt(nextToken());
    }

    private long nextLong(int radix) {
        return parseLong(nextToken(), radix);
    }

    private long nextLong() {
        return parseLong(nextToken());
    }

    private double nextDouble() {
        return parseDouble(nextToken());
    }

    private int[] nextArr(int size) {
        return stream(new int[size]).map(c -> nextInt()).toArray();
    }

    private long[] nextArrL(int size) {
        return stream(new long[size]).map(c -> nextLong()).toArray();
    }

    private double[] nextArrD(int size) {
        return stream(new double[size]).map(c -> nextDouble()).toArray();
    }

    private char[][] nextCharMatrix(int n) {
        return range(0, n).mapToObj(i -> nextToken().toCharArray()).toArray(char[][]::new);
    }

    private int[][] nextIntMatrix(final int n, final int m) {
        return range(0, n).mapToObj(i -> nextArr(m)).toArray(int[][]::new);
    }

    private double[][] nextDoubleMatrix(final int n, final int m) {
        return range(0, n).mapToObj(i -> nextArrD(m)).toArray(double[][]::new);
    }

    private String nextToken() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    private void printf(String format, Object... args) {
        writer.printf(format, args);
    }

    private void print(Object o) {
        writer.print(o);
    }

    private void println() {
        writer.println();
    }

    private void println(Object o) {
        print(o);
        println();
    }

    private void flush() {
        writer.flush();
    }

    private <T, Q> T syncGet(Q q) {
        return null;
    }
}