← 返回题目列表

AtCoder · agc010_e

E. 重新排列

中文机器翻译题面 查看原题

分数: 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