Problem Statement

Larry, who has just learned about the least common multiple, came up with something called "LCM sort".

Here, "LCM sort" is defined as follows:
\(N\) integers (possibly with duplicates) are given, denoted by \(a_i\ (1 \leq i \leq N)\).
Fix \(a_1\), take the least common multiple of each of \(a_2〜a_N\) with \(a_1\), and rearrange them in ascending order of the least common multiple.
(If there are multiple elements with the smallest least common multiple, the one with the smaller value as $a_i$ takes priority.)

Larry
renames the resulting array as \(a_1 \dots a_N\) and continues the operation.
Next, he fixes \(a_2\) (keeping \(a_1\) fixed as well) and performs "LCM sort" on \(a_3〜a_N\).
Next, he fixes \(a_3\), and so on. Find the sequence obtained when this has been continued up to \(a_N\).

(In C/C++ a naive solution barely passes, but there is a way to reduce the computational complexity, so this problem is rated ★４.)

Input

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

The \(1\)st line contains \(N\ (1 \leq N \leq 10000)\), the number of integers.
The \(2\)nd line contains the value of each integer \(a_i\ (1 \leq i \leq N, 1 \leq a_i \leq 10000)\), separated by single-byte spaces.

Output

Output the sequence obtained after continuing from \(a_1\) to \(a_N\), separated by single-byte spaces.
Print a newline at the end.

Sample

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