Separate Even and Odd Integers

Given a list of n integers, your task is to separate them into two sequences: one containing all the even numbers and the other containing all the odd numbers, while preserving their original order.

Formally, if the input sequence is \( A = [a_1, a_2, \dots, a_n] \), you need to output two sequences \( E \) and \( O \) such that:

• \( E \) contains all \( a_i \) where \( a_i \) is even, in the order they appear in \( A \).
• \( O \) contains all \( a_i \) where \( a_i \) is odd, in the order they appear in \( A \).

If one of the sequences is empty, output an empty line for that sequence.

inputFormat

The first line of input contains an integer \( n \) (\( 0 \leq n \leq 10^5 \)), the number of integers.

The second line contains \( n \) space-separated integers.

outputFormat

Print two lines:

• The first line should contain the even integers separated by a space.
• The second line should contain the odd integers separated by a space.

If a list is empty, output an empty line.

## sample

7
12 3 5 8 6 7 4

12 8 6 4
3 5 7

</p>