Rearrange Integers

Given a list of integers, rearrange the list such that all odd numbers come first followed by all even numbers, while preserving the relative order among the odd and even numbers from the original list.

Note that an integer (x) is odd if (x,%,2 \neq 0) and even otherwise.

For example, if the input list is [3, 1, 2, 4, 5, 7, 6], then the output should be [3, 1, 5, 7, 2, 4, 6].

You are required to read the input from stdin and print your answer to stdout.

inputFormat

The input consists of two lines. The first line contains a single integer (n) ((1 \le n \le 10^5)) that represents the number of integers. The second line contains (n) integers separated by spaces.

outputFormat

Output the rearranged list in one line, where the integers are separated by a single space.## sample

7
3 1 2 4 5 7 6

3 1 5 7 2 4 6