Problem Statement

You have $N$ balls of colors $C_1, C_2, \\ldots, C_N$. Here, all colors are represented by an integer between $1$ and $N$ inclusive. You want to arrange the balls on a circle. After you do that, you will count the number of pairs of colors $(X, Y)$ such that $X < Y$ and there exist two adjacent balls of colors $X$ and $Y$.

Find an arrangement that minimizes the number of such pairs. If there are many such arrangements, find any of them.

For example, for balls of colors $1, 1, 2, 3$, if we arrange them as $1, 1, 2, 3$, we get $3$ pairs: $(1, 2), (2, 3), (1, 3)$. If we arrange them as $1, 2, 1, 3$, we get only $2$ pairs: $(1, 2), (1, 3)$.

Solve $T$ test cases for each input file.

Constraints

• $1 \\le T \\le 5 \\cdot 10^4$
• $3 \\le N \\le 2 \\cdot 10^5$
• $1 \\le C_i \\le N$
• The sum of $N$ in one input file doesn't exceed $2\\cdot 10^5$.
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

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

Each case is in the following format:

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

Output

For each test case, output your answer in the following format:

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

Here, $A_i$ is the color of the $i$-th ball (in clockwise order) on the circle in your arrangement.

$(A_1, A_2, \\ldots, A_N)$ should be a permutation of $(C_1, C_2, \\ldots, C_N)$, and the number of pairs of colors $(X, Y)$ such that $X < Y$ and there exist two adjacent balls of colors $X$ and $Y$, should be minimized.

If multiple solutions exist, any of them will be accepted.

Sample Input 1

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

Sample Output 1

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