Segregate Book IDs

You are given a list of book IDs. Your task is to reorder the IDs so that all even numbers appear before the odd numbers while preserving the relative order among the even numbers and among the odd numbers.

Formally, let the input list be \(A = [a_1, a_2, \dots, a_n]\). You need to output a list \(B\) which is the concatenation of \(E\) and \(O\), where:

• \(E\) is the list of all even numbers in \(A\), in the same order as they appear in \(A\).
• \(O\) is the list of all odd numbers in \(A\), in the same order as they appear in \(A\).

For example, if \(A = [3, 8, 5, 6, 12, 7]\), then \(E = [8, 6, 12]\) and \(O = [3, 5, 7]\), and the final output should be [8, 6, 12, 3, 5, 7].

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) representing the number of book IDs. The second line contains \(n\) space-separated integers which represent the book IDs.

outputFormat

Output the rearranged list of book IDs as a single line of space-separated integers to standard output (stdout). Ensure that all even IDs (in their original order) come first, followed by all odd IDs (in their original order). For an input with \(n = 0\), output an empty line.

## sample

6
3 8 5 6 12 7

8 6 12 3 5 7

</p>