Problem Description

In a kindergarten, there are $n$ children, each with a student ID.

The teacher requires: children with odd student IDs stand in one line, and children with even student IDs stand in another line.

Hint:

Odd numbers: digits ending in $1, 3, 5, 7, 9$, which satisfy the condition of having a remainder of $1$ when divided by $2$.

Even numbers: digits ending in $0, 2, 4, 6, 8$, which satisfy the condition of having a remainder of $0$ when divided by $2$.

Input Format

There are two lines in total. The first line contains a number $n$, indicating there are $n$ children.

The second line contains $n$ numbers, where the $i$-th number $a_i$ represents the student ID of the $i$-th child.

Output Format

There are two lines in total. The first line contains some numbers, representing the student IDs of children with odd numbers, output in the same order as they were input.

The second line contains some numbers, representing the student IDs of children with even numbers, output in the same order as they were input.

It is guaranteed that there are both odd and even student IDs among the children.

Sample Input and Output

Input Sample #1

5
1 2 3 4 5

Output Sample #1

1 3 5
2 4

Input Sample #2

5
5 2 3 1 4

Output Sample #2

5 3 1
2 4

Notes

For $20\%$ of the data, $n=2$;
For $40\%$ of the data, $n \le 100$;
For another $20\%$ of the data, $a_i=i$;
For $100\%$ of the data, $n \le 10000, 0 \le a_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分