A regatta crew has a queue of n numbered marker buoys to drop along the course, in a fixed queue order. Race rules require every even-coded buoy to be dropped before any odd-coded buoy. Among buoys sharing the same parity, the crew must drop them in the same relative order they appear in the original queue, since the radio log must stay consistent with the original numbering. Given the queue, output the order in which the buoys should actually be dropped.

Input format

The first line contains a single integer n, the number of buoys. The second line contains n space-separated integers a_1 ... a_n, the buoy codes in original queue order.

Output format

Print the n buoy codes, space-separated on one line, in the required drop order: every even code first (in original relative order), followed by every odd code (in original relative order).

Constraints

• 1 <= n <= 5000
• 0 <= a_i <= 10^9

6
3 1 4 1 5 9

4 3 1 1 5 9

5
2 4 6 8 10

2 4 6 8 10