题目描述

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

对于两个正整数 $i$ 和 $j$, ($1 \le i \le n$)，如果此时数组满足 $a_i+a_j$ 是偶数，则交换 $a_i$ 和 $a_j$ 的值。 现在我们想知道，他在任意次操作之后，能得到的字典序最小的数组是什么？

• 什么是字典序？
  • 对于两个数组 $a$ 和 $b$
  • 找到最小的 $i$ 使得 $a_i \neq b_i$
  • 如果 $a_i \lt b_i$，就说 $a$ 的字典序小于 $b$；
  • 如果 $a_i \gt b_i$，就说 $a$ 的字典序小于 $b$；
  • 如果找不到这样的 i, 那么 $a$ 和 $b$ 中长度小的数组，字典序更小
• 下面的例子都是 $a$ 的字典序小于 $b$ 的字典序
  • $a = [1, 2, 3], b = [1, 3, 2]$
  • $a = [1, 2, 3], b = [1, 2, 3, 4]$

提示：

• 什么样的两个数，它们的和是偶数呢？

输入格式

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

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

输出格式

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

3
3 2 1

1 2 3

2
1 1

1 1

数据规模与限制

• $1 \le n \le 10^5$
• $1 \le a_i \le 10^9$