配点 : $1600$ 点

問題文

黒板に $N$ 個の整数が書かれています。$i$ 番目の整数は $A_i$ です。

高橋君と青木君は以下の手順でこれらの数を一列に並べることにしました。

• 最初に、高橋君が好きな順に一列に並べる。
• 次に、青木君が隣り合う $2$ つの数を選んで入れ替えることを好きな回数だけ繰り返す。 ただし、入れ替える $2$ 数は互いに素でなければならない。

高橋君は最終的な並びが辞書順最小となるように、青木君は最終的な並びが辞書順最大となるように最適に行動するとしたとき、 最終的な数列を求めてください。

制約

• $1 \leq N \leq 2000$
• $1 \leq A_i \leq 10^8$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ … $A_N$

出力

最終的な数列を一行に出力せよ。

5
1 2 3 4 5

5 3 2 4 1

高橋君は与えられた数を $(1,2,3,4,5)$ という順番で並べれば、青木君が最適に動かしても $(5,3,2,4,1)$ となります。

4
2 3 4 6

2 4 6 3