题目描述

给出 $n$ 个数 $a_1,a_2,...,a_n$ ，将其排为序列 $\{p_i\}$ ，满足 $\{前\ i\ 个数的中位数\}$ 单调不降。求字典序最大的 $\{p_i\}$ 。

其中，对于一个长度为 $m$ 的数列，若 $m$ 为奇数，则中位数为从小到大第 $\lceil\frac m2\rceil$ 大的数；若 $m$ 为偶数，则中位数为从小到大第 $\frac m2$ 大和第 $\frac m2+1$ 大的数的平均值。

输入

第一行：一个整数 $T$ ，表示数据组数。

对于每组数据：

第一行：一个整数 $n$ ，表示给出数的个数；
第二行：$n$ 个整数 $a_1,a_2,...,a_n$ ，表示给出的数。

输出

对于每组数据输出一行 $n$ 个整数，表示满足要求的字典序最大的序列 $\{p_i\}$ 。

样例

样例输入

2
5
1 2 3 4 5
8
4 4 3 3 3 2 2 1

样例输出

1 3 2 5 4
3 3 4 3 4 2 2 1

数据范围与提示

对于 $20\%$ 的数据，$n\le 7$ ；
对于 $35\%$ 的数据，$n\le 100$ ；
对于 $50\%$ 的数据，$n\le 1000$ ；
对于另外 $20\%$ 的数据，保证 $a_i$ 互不相同；
对于 $100\%$ 的数据，$1\le T\le 3$ ，$1\le n\le 10^5$ ，$1\le a_i\le 10^9$ 。