问题描述

小蓝所在的王国名为偶数王国，在他们王国中数字的比较遵循以下规则：

1. 奇偶性不同时：偶数总是大于奇数
   数学表达：

   • 若 $a$ 为偶数，$b$ 为奇数，则 $a > b$
   • 若 $a$ 为奇数，$b$ 为偶数，则 $a < b$

2. 奇偶性相同时：比较它们的实际数值大小
   数学表达：

   • 若 $a \mod 2 = b \mod 2$，则按 $a$ 和 $b$ 的实际数值比较

输入格式

• 第一行：一个整数 $N$ ($1 \leq N \leq 10^3$)，表示数组长度
• 第二行：$N$ 个正整数 $A_1, A_2, ..., A_N$ ($1 \leq A_i \leq 10^5$)，表示数组元素

输出格式

• 一行 $N$ 个整数，表示按照偶数王国规则排序后的数组

输入

5
1 2 3 4 5

输出

1 3 5 2 4