题目描述

MJZ 有一个长为 $n$ 的数组 $a$ ，数组的下标为 $1, 2, ..., n$ 。他可以进行任意多次如下这种操作：

• 对于两个正整数 $i$ 和 $j$ $(1 \le i,\ j \le n)$ ，如果此时数组 $a$ 满足 $a_i + a_j$ 是偶数，则交换 $a_i$ 和 $a_j$ 的值。

现在 MJZ 想知道，他在任意次操作之后，能得到的字典序最小的数组是什么？

输入格式

第一行一个正整数 $n$ ，表示数组的长度。

接下来一行 $n$ 个正整数，表示数组中的元素。

输出格式

输出一行 $n$ 个正整数，表示能得到的字典序最小的数组。

样例

样例输入1

3
3 2 1

样例输出1

1 2 3

样例输入2

2
1 1

样例输出2

1 1

数据范围与提示

$1 \le n \le 2 \cdot 10^5$

$1 \le a_i \le 10^9$