题目描述

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

高桥君和青木君按照以下步骤将这些数排列成一行：

• 首先，高桥君可以按照自己喜欢的顺序将这些数排成一行。
• 接着，青木君可以任意多次选择相邻的两个数进行交换，但被交换的两个数必须互质。

假设高桥君总是使最终排列字典序最小，青木君总是使最终排列字典序最大，请你求出最终的数列。

输入格式

输入从标准输入中给出，格式如下：

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

输出格式

请输出最终的数列，用一行表示。

样例 1

输入

5
1 2 3 4 5

输出

5 3 2 4 1

样例 2

输入

4
2 3 4 6

输出

2 4 6 3

说明/提示

限制条件

• $1 \leq N \leq 2000$
• $1 \leq A_i \leq 10^8$

样例解释 1

高桥君如果将给定的数按 $(1,2,3,4,5)$ 的顺序排列，则青木君最优操作后可以变成 $(5,3,2,4,1)$。

由 ChatGPT 4.1 翻译