Александр — известный в узких кругах программист. Однажды он решил наконец-то выйти на улицу и активно провести время с мячом, но первым же ударом он оставил вмятину на новом Rolls-Royce богатого и влиятельного предпринимателя Большого Вовы. Бизнесмен недавно открыл интернет-магазин на популярной торговой площадке «Змей-Горыныч», и предлагает Саше устроиться на работу: если он продемонстрирует свои способности, решив задачу, то получит должность специалиста по безопасности, а в противном случае — должность курьера.
Вам даны \(n\) целых положительных чисел \(a_1, a_2, \dots, a_n\). Используя каждое из данных чисел ровно 1 раз, Вы должны составить такую последовательность \(b_1, b_2, \dots, b_n\), что последовательность \(c_1, c_2, \dots, c_n\) лексикографически максимальна, где \(c_i=GCD(b_1,\dots,b_i)\) — наибольший общий делитель первых \(i\) чисел последовательности \(b\).
Александр сильно испугался условия этой несложной задачи, и поэтому он просит у Вас помощи.
Последовательность \(a\) лексикографически меньше последовательности \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в последовательности \(a\) элемент меньше, чем соответствующий элемент в \(b\).
Выходные данные
На каждый набор входных данных выведите ответ в отдельной строке — искомую последовательность \(b\). Если существует несколько подходящих последовательностей, выведите любую из них.
Примечание
В первом наборе тестовых данных примера есть всего две возможные перестановки \(b\): \([2, 5]\) и \([5, 2]\). В первом случае \(c=[2, 1]\), во втором \(c=[5, 1]\).
В третьем наборе тестовых данных примера число \(9\) должно идти первым в \(b\), а \(GCD(9, 3)=3\), \(GCD(9, 8)=1\), поэтому вторым в \(b\) идёт число \(3\).
В седьмом наборе тестовых данных примера первые четыре числа попарно имеют общий делитель (степень двойки), однако ни одно из них не может идти первым в оптимальной перестановке \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17
|
5 2
8 2 1 3
9 3 8
100 50 25 75 64
42
128 96 80 88 52 7
17 2 4 8 16
|