题目描述

Alice 和 Bob 正在博弈。现在他们面前有一个长度为 $n$ 的正整数序列 $A=\{a_1,a_2,\cdots,a_n\}$。两人各需进行一次操作：

• 首先由 Alice 进行操作，将序列 $A$ 的元素任意重排。
• 然后由 Bob 进行操作，他可以执行以下变换任意次：
  • 选取序列 $A$ 的两个相邻且互质的元素，将它们交换。

Alice 希望最后得到的序列 $A$ 字典序最小，Bob 希望最后得到的序列 $A$ 字典序最大。

两人都执行最优操作，求最后得到的序列 $R=\{r_1,r_2,\cdots,r_n\}$。

输入格式

从文件 permutation.in 中读入数据。

第一行输入一个正整数 $n$，表示序列 $A$ 的长度。
接下来一行，输入 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

输出格式

输出到文件 permutation.out 中。

输出一行 $n$ 个正整数，第 $i$ 个正整数表示 $r_i$。

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

5 3 2 4 1

样例解释 1

一种双方都执行最优操作的方案是：

• Alice 初始时将序列 $A$ 重排为 $\{1,2,3,4,5\}$。
• Bob 执行以下变换：交换 $(4,5)$，交换 $(3,5)$，交换 $(2,5)$，交换 $(1,5)$，交换 $(2,3)$，交换 $(1,3)$，交换 $(1,2)$，交换 $(1,4)$。

得到结果 $R=\{5,3,2,4,1\}$。

样例 2

见附加文件中的 permutation2.in 与 permutation2.ans。

该样例满足 $a_i\le 2000$。

样例 3

见附加文件中的 permutation3.in 与 permutation3.ans。

数据范围与提示

对于 $10\%$ 的数据，$n\le 5$。
对于 $30\%$ 的数据，$n\le 20$。
对于 $60\%$ 的数据，$n\le 100$。
另有 $20\%$ 的数据，$a_i\le 2000$。
对于 $100\%$ 的数据，$1\le n\le 2000$，$1\le a_i\le 10^8$。