Orchard Crate Parity Alignment

A fruit-packing line receives n crates in a queue, each stamped with an integer weight code. Exactly n/2 of the codes are even and n/2 are odd (n is guaranteed to be even and positive).

The line has n conveyor slots numbered 0 to n-1. Because of how the downstream labeling machine is wired, every even-numbered slot must receive a crate with an even weight code, and every odd-numbered slot must receive a crate with an odd weight code.

Among all rearrangements satisfying that rule, the supervisor wants the one requiring the least disruption to arrival order: the relative order in which the even-coded crates originally arrived must be preserved among themselves, and independently, the relative order in which the odd-coded crates originally arrived must be preserved among themselves. Determine the resulting sequence of weight codes across the conveyor slots.

Input format

Line 1: an integer n. Line 2: n space-separated integers, the weight codes in arrival order.

Output format

Print n space-separated integers: the weight codes in slot order 0 to n-1, satisfying the parity and order-preservation rules above.

Constraints

• 2 <= n <= 200000, and n is even.
• 0 <= code <= 1000000000
• Exactly n/2 of the input codes are even and exactly n/2 are odd.

4
4 2 7 1

4 7 2 1

6
5 3 2 8 7 4

2 5 8 3 4 7