E - Rearranging

Contest Duration: 2017-02-04(Sat) 12:00 - 2017-02-04(Sat) 13:50 (local time) (110 minutes) Back to Home

E - Rearranging Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $1600$ 点

問題文

黒板に $N$ 個の整数が書かれています。 $i$ 番目の整数は $A_i$ です。

高橋君と青木君は以下の手順でこれらの数を一列に並べることにしました。

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

高橋君は最終的な並びが辞書順最小となるように、青木君は最終的な並びが辞書順最大となるように最適に行動するとしたとき、最終的な数列を求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$  …  $A_N$

出力

最終的な数列を一行に出力せよ。

入力例 1Copy

Copy

5
1 2 3 4 5

出力例 1Copy

Copy

5 3 2 4 1

高橋君は与えられた数を $(1,2,3,4,5)$ という順番で並べれば、青木君が最適に動かしても $(5,3,2,4,1)$ となります。

入力例 2Copy

Copy

4
2 3 4 6

出力例 2Copy

Copy

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 1Copy

Copy

5
1 2 3 4 5

Sample Output 1Copy

Copy

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 2Copy

Copy

4
2 3 4 6

Sample Output 2Copy

Copy

2 4 6 3