Contest Duration: - (local time) (110 minutes) Back to Home
E - Rearranging /

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

• 最初に、高橋君が好きな順に一列に並べる。
• 次に、青木君が隣り合う 2 つの数を選んで入れ替えることを好きな回数だけ繰り返す。
ただし、入れ替える 2 数は互いに素でなければならない。

### 制約

• 1 ≦ N ≦ 2000
• 1 ≦ A_i ≦ 10^8

### 入力

N
A_1 A_2 … A_N


### 入力例 1

5
1 2 3 4 5


### 出力例 1

5 3 2 4 1


### 入力例 2

4
2 3 4 6


### 出力例 2

2 4 6 3


Score : 1600 points

### Problem Statement

There are N integers written on a blackboard. The i-th integer is A_i.

Takahashi and Aoki will arrange these integers in a row, as follows:

• First, Takahashi will arrange the integers as he wishes.
• Then, Aoki will repeatedly swap two adjacent integers that are coprime, as many times as he wishes.

We will assume that Takahashi acts optimally so that the eventual sequence will be lexicographically as small as possible, and we will also assume that Aoki acts optimally so that the eventual sequence will be lexicographically as large as possible. Find the eventual sequence that will be produced.

### Constraints

• 1 ≦ N ≦ 2000
• 1 ≦ A_i ≦ 10^8

### Input

The input is given from Standard Input in the following format:

N
A_1 A_2 … A_N


### Output

Print the eventual sequence that will be produced, in a line.

### Sample Input 1

5
1 2 3 4 5


### Sample Output 1

5 3 2 4 1


If Takahashi arranges the given integers in the order (1,2,3,4,5), they will become (5,3,2,4,1) after Aoki optimally manipulates them.

### Sample Input 2

4
2 3 4 6


### Sample Output 2

2 4 6 3