B. Ихаб и странный человек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$. Вы можете выполнить следующую операцию с ним столько раз, сколько захотите:

  • Выберите любые два числа $$$i$$$ и $$$j$$$ $$$(1 \le i,j \le n)$$$, такие что сумма $$$a_i+a_j$$$ нечетная, и поменяйте местами $$$a_i$$$ и $$$a_j$$$.

Какой лексикографически минимальный массив вы можете получить?

Массив $$$x$$$ лексикографически меньше чем массив $$$y$$$, если есть такой индекс $$$i$$$, что $$$x_i<y_i$$$, и $$$x_j=y_j$$$ для всех $$$1 \le j < i$$$. Менее формально, в первой позиции $$$i$$$, которая отличается, $$$x_i<y_i$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество чисел в массиве $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) — числа массива $$$a$$$.

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

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

Примеры
Входные данные
3
4 1 7
Выходные данные
1 4 7
Входные данные
2
1 1
Выходные данные
1 1
Примечание

В первом примере вы можете поменять местами $$$1$$$ и $$$4$$$, так как $$$1+4=5$$$ нечетное число.