配点 : $700$ 点

問題文

あなたは、色 $C_1, C_2, \ldots, C_N$ の $N$ 個のボールを持っています。 ここで、すべての色は $1$ 以上 $N$ 以下の整数により表されます。 あなたは、これらのボールを円周上に並べようとしています。その後、色のペア $(X, Y)$ であって、$X < Y$ であり、色 $X$ と $Y$ の二つの隣接するボールが存在するようなペアの個数を数えます。

そのようなペアの個数を最小化する配置を求めてください。そのような配置が多数存在する場合は、そのうちのいずれかを求めてください。

例えば、色 $1, 1, 2, 3$ のボールについて、$1, 1, 2, 3$ と並べると、$(1, 2), (2, 3), (1, 3)$ という $3$ つのペアが現れます。$1, 2, 1, 3$ と並べると、現れるペアは $(1, 2), (1, 3)$ の $2$ つのみです。

各入力ファイルについて、$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$ の二つの隣接するボールが存在するようなペアの個数が最小化されていなければならない。

複数の解が存在する場合は、そのいずれも認められる。

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

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