Someday, It Would Be Nice to Get Sorted

Interview

Time limit2sMemory limit1024 MB

Summary

Adjacent coprime elements may be swapped any number of times; output the lexicographically smallest sequence that can be reached.

Level: Medium6 of 10
Topics: Topological sort, Greedy, Number theory
Solved: No attempts yet

Problem

There is a sequence $A = [A_1, \cdots, A_N]$ of $N$ positive integers. You may perform the following operation as many times as you want. You may also perform no operation at all.

When two adjacent elements of the sequence are coprime, swap the order of those two elements.

Two numbers are coprime when their greatest common divisor is $1$ . After the operations, find the sequence $A$ that is lexicographically smallest.

Input

The first line contains the length of the sequence $N$ . $(1 \leq N \leq 3\,000)$

The second line contains $N$ positive integers $A_1, A_2, \cdots, A_N$ separated by spaces. $(1 \leq A_i \leq 10^9)$

Output

Print the lexicographically smallest sequence $A$ after the operations on one line, with the elements separated by spaces.

Hint

A sequence is lexicographically smaller than another sequence when:

The first element of the smaller sequence is smaller than the first element of the other sequence.
If the first elements are equal, the sequences are compared again after removing the first element, and the one that is smaller in this comparison is lexicographically smaller.

An empty sequence is lexicographically smaller than any other sequence. The lexicographically smallest sequence is one that is less than or equal to every other sequence in lexicographic order.

Examples1

Example 1
Input
```
5
7 3 4 2 6
```
Expected output
```
3 4 2 6 7
```