题目内容

小诚有一个长度为 $n$ 的正整数序列，可以将其重新排列成任意顺序。对于一个连续非空子段 $[i, j]$（$1 \le i \le j \le n$），定义它的协调值 $H(i, j)$ 为最大的正整数 $d$，使得子段中的每一个数都能被 $d$ 整除。记重排后的序列为 $b_1, b_2, \ldots, b_n$，总协调度为

请你找出一种排列，使得 $S$ 达到最大，并输出该排列。

约束：

• 序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 序列中的所有元素均为整数且满足 $1 \le a_i \le 12$。

输入描述

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 第二行包含 $n$ 个整数，表示初始序列的元素，相邻整数之间用空格分隔。每个整数 $a_i$ 满足 $1 \le a_i \le 12$。

输出描述

输出一行，包含 $n$ 个整数，表示重新排列后的序列，相邻整数之间用空格分隔。如果存在多种最优排列，输出任意一种即可。

样例1

输入

1
7

输出

7

说明

序列长度为 1，只有一种排列 [7]。唯一的连续非空子段是 [1,1]，协调值 $H(1,1) = 7$，因此总协调度 $S = 7$。输出 7。

样例2

输入

3
2 3 5

输出

2 3 5

说明

三个元素 2、3、5 两两互质。对于任意排列，长度大于 1 的子段的最大公约数均为 $1$。 长度 1 子段的和为 $2+3+5=10$，长度 2 子段共 3 个，总贡献为 $3 \times 1=3$，长度 3 子段贡献 $1$。总协调度 $S = 10+3+1 = 14$。所有排列的总协调度相同，输出 2 3 5 是一种可行排列。

样例3

输入

3
3 6 12

输出

3 6 12

说明

排列 [3, 6, 12] 可以使总协调度达到最大。 计算该排列的协调度： 长度 1 子段分别为 $3, 6, 12$，和为 $21$； 长度 2 子段：$H(1,2)=\gcd(3,6)=3$，$H(2,3)=\gcd(6,12)=6$，和为 $9$； 长度 3 子段：$H(1,3)=\gcd(3,6,12)=3$，贡献 $3$。 总协调度 $S = 21+9+3 = 33$，是所有排列中的最大值。

样例4

输入

4
2 2 4 4

输出

2 2 4 4

说明

序列包含两个 2 和两个 4。将相同元素相邻排列可最大化总协调度。 排列 [2, 2, 4, 4] 的协调度计算： 长度 1：$2+2+4+4=12$； 长度 2：$\gcd(2,2)=2$，$\gcd(2,4)=2$，$\gcd(4,4)=4$，和为 $8$； 长度 3：$\gcd(2,2,4)=2$，$\gcd(2,4,4)=2$，和为 $4$； 长度 4：$\gcd(2,2,4,4)=2$，贡献 $2$。 总协调度 $S = 12+8+4+2 = 26$，另一种排列 [4, 4, 2, 2] 也得到相同总协调度，输出任意一种即可。