Reorder Array: Segregate Even and Odd Integers

You are given an array of integers. Your task is to rearrange the array so that all even numbers appear before all odd numbers. The relative order among even numbers and odd numbers should be preserved.

Specifically, if the input array is \(A = [a_1, a_2, \ldots, a_n]\), then the output should be a reordered array \(B\) where all \(a_i\) such that \(a_i \equiv 0 \pmod{2}\) come first (in their original order) followed by all \(a_i\) such that \(a_i \not\equiv 0 \pmod{2}\) (also in their original order).

You need to read input from stdin and output the result to stdout.

inputFormat

The first line contains an integer (n) (where (0 \leq n \leq 10^5)), representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output the rearranged array in a single line with its elements separated by spaces. If the array is empty, output an empty line.## sample

4
1 2 3 4

2 4 1 3