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