GCD Table

Time limit2sMemory limit512 MB

Summary

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

Level: Medium7 of 10
Topics: Math, Number theory, Greedy, Hash map
Solved: No attempts yet

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.

Examples3

Example 1

Input

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

Expected output

2 3 4 6

Example 2
Input
```
1
42
```
Expected output
```
42
```
Example 3
Input
```
2
1 1 1 1
```
Expected output
```
1 1
```