题目描述

给定一个由 $n$ 个正整数构成的序列 $A$，请将该序列按照以下规则排序：

• 偶数一定大于奇数（即所有奇数排在前面）；
• 如果两个数奇偶性相同，则按数值从小到大排序。

请输出排序后的序列。

输入格式

第一行一个正整数 $n$，表示序列的长度。 第二行 $n$ 个正整数 $A_1, A_2, \ldots, A_n$，表示序列中的每个数。

输出格式

输出排序后的序列，数字之间用空格隔开。

样例输入

10
1 5 3 2 9 1 2 7 3 4

样例输出

1 1 3 3 5 7 9 2 2 4

数据范围

$1 \le n \le 1000$

$1 \le A_i \le 1000$