题目描述

小易给你一个包含n个数字的数组\(a_1, a_2, \dots, a_3\)。你可以对这个数组执行任意次以下
交换操作：
对于数组中的两个下标i,j(\(1 \leq i, j \leq n\))，如果\(a_i + a_j\)为奇数，就可以交换\(a_i\)和\(a_j\)

现在允许你使用操作次数不限，小易希望你能求出在所有能通过若干次操作可以得到的数组中，字典序最小的一个是什么。

输入描述：

第一行一个整数n;
第二行n个整数\(a_1, a_2, \dots, a_n\), 表示数组，每两个数字之间用一个空格分隔。
输入保证\(1 \leq n \leq 10^5; 1 \leq a_i \leq 10^9\)。

输出描述：

n个整数，每两个整数之间用一个空格分隔，表示得到的字典序最小的数组。

示例1

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

4
7 3 5 1

输出

7 3 5 1

示例2

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

10
53941 38641 31525 75864 29026 12199 83522 58200 64784 80987

输出

12199 29026 31525 38641 53941 58200 64784 75864 80987 83522