背景

于富士山河畔，一个人露营的女孩·凛。
与独自骑着自行车来到富士山的女孩·抚子。

为了让寒冷的身体取暖而点燃篝火的两人。
噼啪噼啪的柴火爆音，沁入湖畔的静寂之中。

围着篝火，一边啜着咖喱面一边对话的抚子和凛。

描述

抚子和凛在玩一个数字游戏。

现在有一个 \(n\) 个数组成的数列 \(a_n\)

首先，抚子可以选择序列的任意排列。然后，凛可以 多次 选择两个相邻的互质的数交换位置。

抚子的目标是使得数列的字典序尽可能的小，凛的目标是使得数列字典序尽可能的大。

在两人均采取最优策略的情况下，请输出最终数列

输入格式

第一行一个正整数 \(n\) ，表示数组长度为 \(n\)

第二行有 \(n\) 个数，表示给定的数列

输出格式

输出一行，元素之间空格隔开

输入输出样例

输入

5
1 2 3 4 5

输出

5 3 2 4 1

说明/提示

【数据范围】

对于 \(30\%\) 的数据：\(1\le n \le 20, 1 \le a_i \le 100\)

对于 \(100\%\) 的数据：\(1 \le n \le 2000, 1 \le a_i \le 10^8\)