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
Comments
Why do I keep getting WA for my submission? I have no clue what I did wrong: https://dmoj.ca/src/5071271