M. Нодные обмены
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

При изучении темы «Делители числа» учитель математики придумал игру «Нодные обмены».

Ребята кружка встают в ряд и у каждого есть табличка с целым неотрицательным числом. Вася может поменять местами двух ребят, таких, что наибольший общий делитель (НОД) чисел на их табличках больше единицы. Задача Васи — путем любого количества обменов получить ряд чисел, который будет лексикографически минимальным.

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

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

В первой строке входных данных находится единственное число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество ребят, которые выстроились в ряд.

Во второй строке находятся $$$n$$$ целых неотрицательных чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^5$$$) — числа на табличках участников кружка.

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

Выведите лексикографически минимальный массив, который можно получить из исходного, применив данную операцию сколького угодно раз.

Примеры
Входные данные
3
6 4 2
Выходные данные
2 4 6
Входные данные
3
10 15 6
Выходные данные
6 10 15
Входные данные
6
12 45 3 8 15 7
Выходные данные
3 8 12 15 45 7
Примечание

В последнем примере чтобы получить ответ, можно было делать такие обмены:

12 45 3 8 15 7 $$$\rightarrow$$$ 3 45 12 8 15 7 (меняем 12 и 3)

3 45 12 8 15 7 $$$\rightarrow$$$ 3 15 12 8 45 7 (меняем 45 и 15)

3 15 12 8 45 7 $$$\rightarrow$$$ 3 12 15 8 45 7 (меняем 15 и 12)

3 12 15 8 45 7 $$$\rightarrow$$$ 3 8 15 12 45 7 (меняем 12 и 8)

3 8 15 12 45 7 $$$\rightarrow$$$ 3 8 12 15 45 7 (меняем 15 и 12)