Reorder Even and Odd Integers

You are given a list of integers. Your task is to rearrange the list such that all even numbers appear before all odd numbers while preserving the relative order among even numbers and among odd numbers.

Note: If the list is empty, simply output an empty line.

Examples:

Input:
6
1 2 3 4 5 6
Output:
2 4 6 1 3 5
Input:
4
3 1 2 4
Output:
2 4 3 1

</p>

The solution should read input from stdin and output the result to stdout.

inputFormat

The first line of input contains an integer n representing the number of integers in the list.

The second line contains n space-separated integers.

outputFormat

Output a single line with the reordered list of integers. All even numbers should appear first in their original order, followed by all odd numbers in their original order. The numbers must be separated by a space. If the list is empty, output an empty line.

## sample

6
1 2 3 4 5 6

2 4 6 1 3 5