Even-Odd Reordering

Given an array of integers, reorder the array so that the even numbers come first, followed by the odd numbers, while preserving the relative order of the even and odd numbers.

More formally, for any integer x in the array, if it satisfies the condition $$ x \mod 2 = 0 $$ then it is considered even and should appear before any odd numbers in the output.

The input is read from the standard input (stdin) and the output is written to the standard output (stdout). Make sure your solution handles edge cases such as an empty array or arrays with a single element.

inputFormat

The first line of input contains a single integer n (0 ≤ n ≤ 10⁵), representing the number of elements in the array.

The second line contains n space-separated integers where each integer is in the range of a typical 32-bit signed integer.

outputFormat

Output a single line containing the reordered array. All even numbers should appear first in the original order, followed by all odd numbers in their original order. The numbers must be printed separated by a single space.

## sample

4
3 1 2 4

2 4 3 1

</p>