您有 $$$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$$$ 的重新排列版本。如果有多个有效的重新排列,则打印其中任何一个。
示例
输入 #1
2 6 5 -2 4 8 6 5 4 8 1 4 2
输出 #1
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”。