Separate and Sort Integers

You are given a list of integers. Your task is to separate the list into two lists: one containing all the even numbers and the other all the odd numbers. Both lists must be sorted in ascending order.

The input will be provided via standard input (stdin) and the output should be printed to standard output (stdout). The first line of input contains a single integer n — the number of integers in the list. The second line contains n space-separated integers.

Your program should output two lines. The first line should contain the sorted even numbers separated by a space. The second line should contain the sorted odd numbers separated by a space. If a list is empty, output an empty line for that list.

Note: Use \( \LaTeX \) for any formulas. For example, the number of elements is given by \( n \), and the sorting order is ascending.

inputFormat

The first line contains a non-negative integer \( n \), representing the number of elements in the list. The second line contains \( n \) space-separated integers.

outputFormat

The output consists of two lines. The first line contains the even numbers in ascending order separated by spaces. The second line contains the odd numbers in ascending order separated by spaces. If there are no even or odd numbers, print an empty line for that group.

## sample

6
5 3 2 8 1 4

2 4 8
1 3 5

</p>