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.util.*;

public class CodeforcesB {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);


        int t = input.nextInt();

        for (int i = 0; i < t; i++) {
            doTestCase(input);
        }

    }

    private static void removeFromMap(int toRemove, Map<Integer, Integer> map) {
        Integer count = map.remove(toRemove);

        count--;

        if (count != 0) {
            map.put(toRemove, count);
        }
    }

    private static void addToMap(int toAdd, Map<Integer, Integer> map) {
        Integer count = map.get(toAdd);
        if (count == null) {
            count = 0;
        }
        count++;

        map.put(toAdd, count);
    }

    private static int findHighestDiff(int number, TreeMap<Integer, Integer> map) {
        Integer first = map.firstKey();
        Integer last = map.lastKey();
        if (first == null) {
            return last;
        }
        if (last == null) {
            return first;
        }


        if (Math.abs((long) first - number) > Math.abs((long) last - number)) {
            return first;
        } else {
            return last;
        }
    }
    private static int findSmallestDiff(int number, TreeMap<Integer, Integer> map) {
        Integer floor = map.floorKey(number);
        Integer ceil = map.ceilingKey(number);
        if (floor == null) {
            return ceil;
        }
        if (ceil == null) {
            return floor;
        }


        if (Math.abs(number - (long) floor) < Math.abs(number - (long) ceil)) {
            return floor;
        } else {
            return ceil;
        }
    }

    private static void doTestCase(Scanner input) {
        int n = input.nextInt();

        TreeMap<Integer, Integer> map = new TreeMap<>();


        long highestDiff = 0;
        int last = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int number = input.nextInt();
            last = number;
            addToMap(number, map);
        }




        for (int potentialLast : new ArrayList<>(map.keySet())) {
            removeFromMap(potentialLast, map);
            if (map.isEmpty()) {
                addToMap(potentialLast, map);
                break;
            }
            int highestDiffNumber = findHighestDiff(potentialLast, map);
            long diff = Math.abs((long) highestDiffNumber - potentialLast);

            if (highestDiff < diff) {
                highestDiff = diff;
                last = potentialLast;
            }
            addToMap(potentialLast, map);
        }


        removeFromMap(last, map);

        List<Integer> sortedList = new ArrayList<>();
        sortedList.add(last);

        int current = last;
        while (!map.isEmpty()) {
            int highestDiffNumber = findHighestDiff(current, map);
            current = highestDiffNumber;
            removeFromMap(highestDiffNumber, map);
            sortedList.add(highestDiffNumber);
        }

        Collections.reverse(sortedList);
        for (Integer number : sortedList) {
            System.out.print(number + " ");
        }
        System.out.println();

//        for (int i = 0; i < sortedList.size() - 1; i++) {
//            System.out.print(Math.abs(sortedList.get(i) - (long)sortedList.get(i + 1)) + " ");
//        }



    }
}