You have a one-indexed array $a$ of length $N$. This array is special: each value will occur at most $K$ times in the array.

You also decided on a value $d$, where $d>1$. You can then perform the following operation any number (possibly zero) of times:

• Choose an index $i$ ($1\le i\le N-d)$, and swap $a_i$ with $a_{i+d}$.

Please output the lexicographically smallest array that can be made if you choose the optimal value of $d$. An array $a$ is lexicographically smaller than an array $b$ if there is some index $i$ such that $a_i<b_i$ and $a_j=b_j$ for all $j<i$.

Input Specification

The first line will contain the integer $N$ $(1\le N\le 5\times {10}^4)$.

The next line will contain $N$ integers, $a_i$ $(1\le a_i\le {10}^9)$. It is guaranteed that each value of $a_i$ will occur at most $K$ times.

Output Specification

Output the lexicographically smallest array that can be made if the optimal value of $d$ is chosen.

Subtasks

Subtask 1 [12%]

$K=1$

Subtask 2 [27%]

$K\le 4$

Subtask 3 [61%]

$K\le 500$

Sample Input for Subtask 1

5
5 4 3 2 1

Sample Output for Subtask 1

1 2 3 4 5

Sample Input for Subtask 2

6
3 1 1 1 1 2

Sample Output for Subtask 2

1 1 1 1 3 2

Explanation for Sample for Subtask 2

One optimal value of $d$ is $4$.

Sample Input for Subtask 3

11
5 1 2 1 2 1 2 1 1 2 100

Sample Output for Subtask 3

1 1 1 1 2 5 2 2 1 2 100