Optimal Priority (Lexicographic Sort with Parity Swap)

Each time, you may only swap two adjacent items with different parity. Find the lexicographically smallest sequence that can be reached. Each item is a single digit.

输入格式

The first line contains n, and the second line contains the digits. On this site 1≤n≤200000, 0≤digit≤9.

输出格式

Output the full minimum sequence.

样例 1

输入：

6
2 4 6 4 3 2

输出：

2 3 4 6 4 2

样例 2

输入：

3
9 7 2

输出：

2 9 7

样例 3

输入：

1
0

输出：

0

样例说明

The examples give 2 3 4 6 4 2; 2 9 7; and 0 respectively.