Maximize Sequence by Even Sum Swaps

You are given an integer (n) and a list of (n) integers. You are allowed to swap two adjacent elements of the list if the sum of these two elements is even. This is equivalent to saying that two adjacent elements can be swapped if they are both even or both odd (i.e., (a + b) is even if and only if (a) and (b) have the same parity).

The goal is to obtain a sequence which is maximized in lexicographical order by performing any number of allowed swaps. An optimal strategy is to sort the list in descending order, separate the numbers based on their parity, and then merge the lists by alternating even and odd numbers where possible. This approach derives from the fact that numbers of the same parity can be rearranged arbitrarily via allowed swaps.

Example:
For (n = 5) and the list [1, 2, 3, 4, 5], after sorting in descending order we obtain [5, 4, 3, 2, 1]. Separating into evens and odds gives: evens = [4, 2] and odds = [5, 3, 1]. Merging them alternately yields the final sequence: [4, 5, 2, 3, 1].

inputFormat

The input is read from stdin and consists of two lines. The first line contains a single integer (n) ((1 \leq n \leq 10^5)) representing the number of elements. The second line contains (n) space-separated integers.

outputFormat

Output the final sequence as a single line to stdout. The numbers should be space-separated.## sample

5
1 2 3 4 5

4 5 2 3 1