Alice把自己的玩具排成一排，第i个玩具有一个互不相同的整数a_i表示这个玩具的属性，现在用玩具的属性代表玩具，她想把玩具重新排序，可以进行任意次以下操作：
Alice每次只能在数组中选择两个数，如果这两个数具有不同的奇偶性，就可以交换这两个玩具。
现在Alice想知道能够排出的字典序最小的数组，请输出排序后的数组。
如果存在一个索引 i 使得 p_j=q_j 对应所有 j<i 和 p_i<q_i ，则序列 p 在字典顺序上小于序列 q。

第一行输入一个整数n（1 <= n <= 1000）
第二行输入数组a

输出排序后字典序最小的数组

第一次可以选择2和1进行交换，此时数组为：1 3 2 4
第二次可以换则3和2进行交换，此时数组为：1 2 3 4，字典序最小。