B. Отсортированные разности соседних
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив из $$$n$$$ чисел $$$a_{1}, a_{2}, \ldots, a_{n}$$$.

Переставьте эти числа так, чтобы они удовлетворяли $$$|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$$$, где $$$|x|$$$ обозначает абсолютное значение $$$x$$$. Гарантируется, что для данных ограничений всегда можно найти такую перестановку.

Обратите внимание, что элементы в $$$a$$$ не обязательно попарно различны. Другими словами, некоторые элементы $$$a$$$ могут быть одинаковыми.

Вы должны ответить на $$$t$$$ независимых тестовых случаев.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$)  — количество тестовых случаев.

Первая строка каждого тестового случая содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^{5}$$$)  — длину массива $$$a$$$. Гарантируется, что сумма значений $$$n$$$ по всем тестовых случаях не превышает $$$10^{5}$$$.

Вторая строка каждого тестового случая содержит $$$n$$$ целых чисел $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$).

Выходные данные

Для каждого тестового случая выведите перестановку массива $$$a$$$, которая удовлетворяет данному условию. Если существует несколько допустимых перестановок, выведите любую из них.

Пример
Входные данные
2
6
5 -2 4 8 6 5
4
8 1 4 2
Выходные данные
5 5 4 6 8 -2
1 2 4 8
Примечание

В первом тестовом случае, для данной перестановки, мы имеем $$$|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$$$. Существуют также другие ответы, к примеру "5 4 5 6 -2 8".

Во втором тестовом случае, для данной перестановки, мы имеем $$$|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$$$. Существуют также другие ответы, к примеру "2 4 8 1".