У вас есть массив из \(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\) независимых тестовых случаев.
Выходные данные
Для каждого тестового случая выведите перестановку массива \(a\), которая удовлетворяет данному условию. Если существует несколько допустимых перестановок, выведите любую из них.
Примечание
В первом тестовом случае, для данной перестановки, мы имеем \(|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".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6
5 -2 4 8 6 5
4
8 1 4 2
|
5 5 4 6 8 -2
1 2 4 8
|