Sort Even and Odd Numbers

You are given an array of integers. Your task is to rearrange the array such that all even numbers come before all odd numbers while maintaining the original relative order among even numbers and among odd numbers. An integer \(k\) is even if \(k \equiv 0 \pmod{2}\), and odd otherwise.

Example:
If the input is [1, 2, 4, 3, 5, 6], the even numbers are [2, 4, 6] and the odd numbers are [1, 3, 5]. The final sorted array should be [2, 4, 6, 1, 3, 5].

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing the array.

outputFormat

Output the rearranged array in one line. The even numbers are listed first, followed by the odd numbers, both preserving their original order. Each number should be separated by a single space. If the array is empty, output nothing.

6
1 2 4 3 5 6

2 4 6 1 3 5