← 返回题目列表

Codeforces · 977/D

D. 除以三,乘以二

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

坡旅甲喜欢玩数字。他取一些整数 $$$x$$$,将其写在黑板上,然后用它执行 $$$n - 1$$$ 两种运算:

- 将数字 $$$x$$$ 除以 $$$3$$$ ($$$x$$$ 必须能被 $$$3$$$ 整除);
- 将数字 $$$x$$$ 乘以 $$$2$$$。

每次操作后,Polycarp 将结果写在黑板上,并用结果替换 $$$x$$$。所以棋盘上毕竟会有 $$$n$$$ 数字。

给你一个长度为 $$$n$$$ 的序列——波利卡普写下的数字。该序列以任意顺序给出,即序列的顺序可能与板上写的数字的顺序不匹配。

你的问题是重新排列(重新排序)这个序列的元素,使其能够按照棋盘上写的数字的顺序匹配可能的波利卡普的游戏。 IE。下一个数字将恰好是前一个数字的两倍,或者恰好是前一个数字的三分之一。

保证答案存在。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 序列中元素的数量。输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^{18}$$$) — Polycarp 可以在黑板上写下的重新排列(重新排序)的序列。

输出

打印 $$$n$$$ 整数 — 重新排列(重新排序)的输入序列,可以是 Polycarp 可以在黑板上写下的序列。

保证答案存在。

示例

输入 #1

6
4 8 6 3 12 9

输出 #1

9 3 6 12 4 8

输入 #2

4
42 28 84 126

输出 #2

126 42 84 28

输入 #3

2
1000000000000000000 3000000000000000000

输出 #3

3000000000000000000 1000000000000000000

注意

在第一个示例中,给定的序列可以按以下方式重新排列:$$$[9, 3, 6, 12, 4, 8]$$$。它可以匹配可能的Polycarp 的以$$$x = 9$$$ 开始的游戏。