Separate Even and Odd Numbers

You are given a list of non-negative integers. Your task is to separate the list into two lists: one containing all the even numbers and the other containing all the odd numbers. The relative order of the numbers in each list should be the same as in the input.

Input Format: The first line contains a single integer n which denotes the number of integers. The second line contains n space-separated non-negative integers.

Output Format: Print two lines. The first line should contain the even numbers separated by a space (or an empty line if there are no even numbers). The second line should contain the odd numbers separated by a space (or an empty line if there are no odd numbers).

Example:

Input:
10
1 2 3 4 5 6 7 8 9 10
Output:
2 4 6 8 10
1 3 5 7 9

</p>

Make sure your program reads from standard input and writes to standard output.

inputFormat

The first line contains an integer n -- the number of non-negative integers. The second line contains n space-separated integers.

outputFormat

Print two lines. The first line contains the even numbers (in order) separated by spaces. The second line contains the odd numbers (in order) separated by spaces. If a list is empty, print an empty line for that list.

## sample

10
1 2 3 4 5 6 7 8 9 10

2 4 6 8 10
1 3 5 7 9

</p>