题目描述

黑板上写着 $N$ 个整数。第 $i$ 个整数为 $A_i$。

高桥和青木将按照以下规则排列这些整数：

• 首先，高桥可以自行决定整数的排列顺序。
• 然后，青木可以任意多次交换相邻的互质整数。

我们假设高桥采取最优策略以使得最后的排列是字典序最小的，同时我们也假设青木采取最优策略以使得最后的排列是字典序最大的。请找出最终的排列。

约束条件

• $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

如果高桥按照给定的顺序 $(1,2,3,4,5)$ 排列整数，那么经过青木的最佳操作后得到的排列是 $(5,3,2,4,1)$。

示例 2

4
2 3 4 6

输出 2

2 4 6 3