Reorder Array: Even Numbers First

You are given an array of integers. Your task is to reorder the array so that all even numbers come before all odd numbers while preserving the original relative order among the even numbers and among the odd numbers.

In mathematical terms, if the input array is \(A = [a_1, a_2, \ldots, a_n]\), you need to produce a new array \(B\) such that:

\(B = [\text{all even elements of } A] \Vert [\text{all odd elements of } A]\),

where \(\Vert\) denotes array concatenation. For example, if \(A = [4, 1, 3, 2, 5]\), then the output should be \([4, 2, 1, 3, 5]\).

The input may contain negative numbers and zeros. If the array is empty, simply output an empty line.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers.

If \(n = 0\), the second line will be empty.

outputFormat

Output the reordered array on a single line with each number separated by a single space. The output should be sent to standard output (stdout).

## sample

5
4 1 3 2 5

4 2 1 3 5