Arrange Kindergarten Children by ID Parity

There are (n) children in a kindergarten, each with a unique ID number. The teacher requires that the children with odd IDs and the children with even IDs stand in separate lines. A number is considered odd if its last digit is one of ({1, 3, 5, 7, 9}) and satisfies (n \bmod 2 = 1). A number is considered even if its last digit is one of ({0, 2, 4, 6, 8}) and satisfies (n \bmod 2 = 0).

Your task is to read the number of children and the list of ID numbers, then output two lines. The first line contains all the odd ID numbers (in the same order as input) and the second line contains all the even ID numbers (in the same order as input). If one of the groups is empty, output an empty line for that group.

inputFormat

The first line contains an integer (n) representing the number of children. The second line contains (n) space-separated integers representing the ID numbers.

outputFormat

Output two lines. The first line should contain all the odd ID numbers (if any) separated by spaces. The second line should contain all the even ID numbers (if any) separated by spaces.

sample

5
1 2 3 4 5

1 3 5
2 4