题目描述

你有 $N$ 个颜色为 $C_1, C_2, \ldots, C_N$ 的球。这里，所有的颜色都用 $1$ 到 $N$ 之间的整数表示。你想把这些球排列在一个圆上。排列完成后，你将计算颜色对 $(X, Y)$ 的数量，其中 $X < Y$ 并且存在两个相邻的球的颜色分别为 $X$ 和 $Y$。

找到一种最小化这样的颜色对数量的排列。如果有多种排列方式，任意一种都可以。

例如，对于颜色为 $1, 1, 2, 3$ 的球，如果我们将它们排列为 $1, 1, 2, 3$，我们会得到 $3$ 对颜色：$(1, 2), (2, 3), (1, 3)$。如果我们将它们排列为 $1, 2, 1, 3$，我们只会得到 $2$ 对颜色：$(1, 2), (1, 3)$。

解决每个输入文件的 $T$ 个测试用例。

约束条件

• $1 \le T \le 5 \cdot 10^4$
• $3 \le N \le 2 \cdot 10^5$
• $1 \le C_i \le N$
• 一个输入文件中 $N$ 的总和不超过 $2\cdot 10^5$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例都以以下格式给出：

$N$ $C_1$ $C_2$ $\ldots$ $C_N$

输出

对于每个测试用例，将答案以以下格式输出：

$A_1$ $A_2$ $\ldots$ $A_N$

这里，$A_i$ 是在你的排列中圆上第 $i$ 个球的颜色（顺时针）。

$(A_1, A_2, \ldots, A_N)$ 应该是 $(C_1, C_2, \ldots, C_N)$ 的一个排列，并且颜色对 $(X, Y)$ 的数量，其中 $X < Y$ 并且存在两个相邻的球的颜色分别为 $X$ 和 $Y$，应该最小化。

如果有多个解决方案，任何一个都将被接受。

样例输入 1

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

样例输出 1

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