Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Подели на три, умножь на два
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп любит играть с числами. Он берет некоторое целое положительное число $$$x$$$, выписывает его на доску, и выполняет с ним $$$n - 1$$$ операцию двух видов:

  • поделить число $$$x$$$ на $$$3$$$ (число $$$x$$$ должно быть кратно $$$3$$$);
  • умножить число $$$x$$$ на $$$2$$$.

После каждой операции Поликарп выписывает результат операции на доску, а число $$$x$$$ заменяет на результат операции. Таким образом, на доске окажутся ровно $$$n$$$ чисел.

Вам задана последовательность длины $$$n$$$ — числа, которые выписал Поликарп. Эта последовательность задана в произвольном порядке, то есть порядок чисел может не соответствовать порядку их записи на доску.

Ваша задача — переупорядочить элементы последовательности так, чтобы она соответствовала возможной игре Поликарпа в порядке записи чисел на доску. Таким образом, каждое следующее число в последовательности должно быть либо ровно в три раза меньше предыдущего, либо ровно в два раза больше предыдущего.

Гарантируется, что ответ существует.

Входные данные

Первая строка входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество элементов в последовательности. Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^{18}$$$) — переупорядоченная последовательность, которую Поликарп выписал на доску.

Выходные данные

Выведите $$$n$$$ целых чисел — переупорядоченную последовательность из входных данных, которая может быть последовательностью, которую Поликарп выписал на доску.

Гарантируется, что ответ существует.

Примеры
Входные данные
6
4 8 6 3 12 9
Выходные данные
9 3 6 12 4 8
Входные данные
4
42 28 84 126
Выходные данные
126 42 84 28
Входные данные
2
1000000000000000000 3000000000000000000
Выходные данные
3000000000000000000 1000000000000000000
Примечание

В первом примере заданную последовательность можно переупорядочить следующим образом: $$$[9, 3, 6, 12, 4, 8]$$$. Это соответствует возможной игре Поликарпа, начиная с $$$x = 9$$$.