Mr. Gregory recently discovered the existence of ~\gcd~. Enthralled by its beauty, he challenges you to a puzzle. Mr. Gregory gives you a target permutation ~T~ of the integers ~1, 2, \dots, N~. He tells you that a permutation ~P~ is good if it can be turned into ~T~ using the following operation any number of times: choose an integer ~i~ ~(1 \le i \le N-1)~, such that ~\gcd(P_i, P_{i+1}) = 1~, and swap elements ~P_i~ and ~P_{i+1}~. The answer to the puzzle is the lexicographically maximal good permutation ~P~.

Prove your worth by solving the puzzle!

Constraints

~1 \le N \le 5 \times 10^5~

~1 \le T_i \le N~

~T~ is a permutation of the integers ~1, 2, \dots, N~.

Subtask 1 [40%]

~1 \le N \le 3 \times 10^3~

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains the integer ~N~.

The next line contains ~N~ space-separated integers, representing the target permutation ~T~.

Output Specification

Output ~N~ space-separated integers ~P_1, P_2, \dots, P_N~, the lexicographically maximal good permutation ~P~.

Sample Input

4
2 1 3 4

Sample Output

3 2 4 1