分数: 1600 点
问题陈述
有 N 整数写在黑板上。的 i- 第一个整数是 A_i.
Takahashi 和 Aoki 将这些整数排列成一行,如下所示:
- 首先,高桥将按照他的意愿排列整数。
- 然后,Aoki 将重复交换两个互质的相邻整数,次数不限。
我们将假设 Takahashi 采取最佳行动,以便最终序列按字典顺序尽可能小,并且我们还将假设 Aoki 采取最佳行动,以便最终序列按字典顺序尽可能大。 找到将产生的最终序列。
约束
- 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
如果 Takahashi 按顺序排列给定的整数 (1,2,3,4,5),他们将成为 (5,3,2,4,1) 在青木最佳地操纵它们之后。
示例输入 2
4 2 3 4 6
示例输出 2
2 4 6 3