Старец Летовец, известный своими суперскиллами, решил научить своих учеников создавать "Последовательность Трёх Сил". Он дал им список чисел и сказал: "Отсортируйте эти числа так, чтобы они образовали Последовательность Трёх Сил. Вот правила:"
-
Сила Тройки. Числа, которые делятся на 3, должны идти первыми.
-
Сила Порядка. Среди чисел, делящихся на 3, меньшие числа должны идти перед большими.
-
Сила Простоты. Среди чисел, не делящихся на 3, числа имеющие большее количество делителей должны идти раньше, чем числа имеющие меньшее количество делителей. При равном числе делителей, числа должны идти в порядке убывания.
Напишите программу, которая реализует это правило, и создаёт Последовательность Трёх Сил из любого списка целых чисел.
Формат входных данных
В первой строке записано натуральное число n (n <= 105) - количество целых чисел в списке. Далее, в n строках записано по одному целому числу numi ( -105 <= numi <= -105).
Формат выходных данных
Выведите в одной единственной строке Последовательность Трёх Сил, составленную из исходного списка чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8
3
-24
-13
12
|
-24 3 12 8 -13
|