Вам дан массив \(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\) и \(4\), так как \(1+4=5\) нечетное число.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 1 7
|
1 4 7
|
|
2
|
2
1 1
|
1 1
|