GCD Table

Given all N^2 pairwise gcd values of a hidden sequence in random order, recover the sequence.

Medium7MathNumber theoryGreedyHash mapNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

For a sequence $A = (a_1, a_2, \dots, a_N)$ of length $N$ , the GCD table $G$ is defined by

$g_{ij} = \gcd(a_i, a_j)$

where $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$ . For example, the GCD table of $A = (4, 3, 6, 2)$ is

	4	3	6	2
4	4	1	2	2
3	1	3	3	1
6	2	3	6	2
2	2	1	2	2

All $N^2$ values of the GCD table $G$ are given in arbitrary order. Restore the original sequence $A$ .

Input

The first line contains the length $N$ of the sequence $A$ ( $1 \le N \le 500$ ).

The second line contains the $N^2$ values of the GCD table in arbitrary order, separated by spaces. Every value is a positive integer no larger than $1{,}000{,}000{,}000$ . The input always admits an answer.

Output

Print the $N$ elements of the restored sequence on one line, separated by single spaces.

Any ordering of the elements gives the same GCD table, so print them in non-decreasing order. That is the lexicographically smallest answer. The multiset of elements is uniquely determined.