LogiQuest

433. Sort Array by Parity (Stable)

EasyArray

Print the even numbers first and then the odd numbers, each group keeping its original order.

Input format

Line 1: n Line 2: n integers

Output format

The rearranged array.

Example 1

Input

4
3 1 2 4

Output

2 4 3 1

Example 2

Input

1
0

Output

0

Constraints

1 ≤ n ≤ 10⁵

Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.

Loading the MyLoginn IDE…