Partition and Sort

You are given a list of integers. Your task is to separate this list into two groups: the even numbers and the odd numbers. After partitioning, sort each group in ascending order.

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

Output Format: Print two lines. The first line should contain the sorted even numbers (space-separated). The second line should contain the sorted odd numbers (space-separated). If a group is empty, print an empty line for that group.

Example:

Input:
7
4 1 7 10 3 8 5
Output:
4 8 10
1 3 5 7

</p>

Note: Use standard input (stdin) to read the data and standard output (stdout) to print the results.

inputFormat

The input starts with an integer n (0 ≤ n ≤ 10⁵), which denotes the number of elements in the list. The next line contains n space-separated integers. The integers can be negative or positive.

outputFormat

Output consists of two lines. The first line contains the sorted even numbers separated by a space. The second line contains the sorted odd numbers separated by a space. If a group is empty, output an empty line for that group.

## sample

7
4 1 7 10 3 8 5

4 8 10
1 3 5 7

</p>