Sayaka Saeki является членом студенческого совета, в который входит \(n\) других членов (не считая Sayaka). \(i\)-й член совета имеет высоту \(a_i\) миллиметров.
Наступает конец учебного года, и Sayaka хочет сфотографировать всех остальных членов студенческого совета. Будучи трудолюбивой девушкой и перфекционисткой, она хочет выстроить всех членов в ряд таким образом, чтобы количество последовательных пар фотогеничных членов было как можно больше.
Пара из двух последовательных членов совета \(u\) и \(v\) в строке считается фотогеничной, если их средний рост — целое число, т.е. \(\frac{a_u + a_v}{2}\) — целое число.
Помогите Sayaka расположить остальных членов в ряд таким образом, чтобы максимизировать количество фотогеничных последовательных пар.
Выходные данные
Для каждого набора входных данных выведите в одной строке \(n\) целых чисел — высоты других членов в порядке, который дает наибольшее количество фотогеничных последовательных пар. Если таких порядков несколько, выведите любой из них.
Примечание
В первом наборе входных данных есть одна фотогеничная пара: \((1, 1)\) — фотогенична, так как \(\frac{1+1}{2}=1\) — целое число, а \((1, 2)\) — нет, так как \(\frac{1+2}{2}=1.5\) — нецелое число.
Во втором наборе входных данных обе пары фотогеничны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 1 2
3
1 1 1
8
10 9 13 15 3 16 9 13
2
18 9
|
1 1 2
1 1 1
13 9 13 15 3 9 16 10
9 18
|