Special Sort: Even Numbers First

You are given a list of integers. Your task is to rearrange the list such that all the even numbers appear before the odd numbers. The even numbers should retain their original relative order, as should the odd numbers.

For example, if the input list is [3, 1, 2, 4, 7, 9, 6], then the even numbers (2, 4, 6) remain in the same order and appear first, followed by the odd numbers (3, 1, 7, 9) in their original order. Thus, the output will be [2, 4, 6, 3, 1, 7, 9].

Note: If the list is empty, simply output an empty list, and if the list contains either all even or all odd numbers, output the list unchanged.

The problem can be formalized as follows:

Given an integer \(n\) and a list of \(n\) integers \(a_1, a_2, \dots, a_n\), rearrange the list so that: \[ \{a_i \mid a_i \text{ is even}\} \cup \{a_i \mid a_i \text{ is odd}\} \] where the original order among even and odd numbers is preserved.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
 a1 a2 ... an

Here, \(n\) is an integer representing the number of elements in the list, and the next line contains \(n\) space-separated integers.

outputFormat

Output the sorted list in a single line to standard output (stdout) with each number separated by a space.

## sample

7
3 1 2 4 7 9 6

2 4 6 3 1 7 9