問題文

最小公倍数を習ったばかりのLarryは、最小公倍数ソートというのを思いついた。

ここで「最小公倍数ソート」とは、
\(N\)個の整数（重複を含む）が与えられ、それぞれ\(a_i\ (1 \leq i \leq N)\)とする。
\(a_1\)を固定し、\(a_2〜a_N\)をそれぞれ\(a_1\)に対して最小公倍数を取り、最小公倍数が小さい順に並べ変えるソートのことであるとする。
（最小公倍数の最小が複数ある場合は、$a_i$としての値が少ない方が優先される）

Larryは、
この時出来た配列を新たに\(a_1 \dots a_N\)の名前をつけなおして操作を続ける。
次に\(a_2\)を固定し(\(a_1\)も固定したまま）、\(a_3〜a_N\)を「最小公倍数ソート」していく。
次に\(a_3\)を固定し...と続けていった時に\(a_N\)まで行った時になる数列を求めてください。

（C/C++だと愚直な解法でぎりぎり通ってしまいますが、計算量が抑えられる方法があるので★４になってます。）

入力

\(N\)
\(a_1\ a_2\ \dots\ a_i\ \dots\ a_N\)

\(1\)行目は整数の数を表す\(N\ (1 \leq N \leq 10000)\)が与えられる。
\(2\)行目は各整数の値\(a_i\ (1 \leq i \leq N, 1 \leq a_i \leq 10000)\)を半角スペース区切りとして与えられる。

出力

\(a_1\)から\(a_N\)まで続けていった時の数列を半角スペース区切りで出力してください。
最後に改行してください。

サンプル

5
1 2 3 4 5

1 2 4 3 5

5
4 8 1 2 4

4 1 2 4 8

10
9 9 3 7 5 9 1 5 2 1

9 1 1 2 3 9 9 5 5 7