問題文


任意の整数の偉さを、の最大の素因数で定義します。 長さの配列が与えられるので、の要素を偉さの昇順に並び変えてください。 同じ偉さの整数が複数ある場合は、小さい数ほど前にくるようにしてください。

制約


入力


入力はすべて整数である。

N
a1 a2 ... aN

出力


を条件の通りに並び替えたものを出力してください。

サンプル


入力1
5
2 21 16 9 5
出力1
2 16 9 5 21

の偉さは順に、なので、上の通りに並び替えて出力してください。

入力2
10
6766 4987 3057 3025 3611 2992 5435 250 5206 1378 
出力2
250 3025 2992 1378 5206 3611 6766 3057 5435 4987 

提出


Go (1.14)