Sort Even Numbers Before Odd Numbers

You are given a list of integers. Your task is to rearrange the list such that all the even numbers appear before all the odd numbers while preserving the original relative order within the even and odd groups. In other words, if we denote an even number by \(x\) (i.e., \(x \bmod 2 = 0\)) and an odd number by \(y\) (i.e., \(y \bmod 2 \neq 0\)), then the final list should list all elements \(x\) in their original order and then all elements \(y\) in their original order.

inputFormat

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

outputFormat

Output a single line containing the rearranged list of integers where the even numbers appear first (in the same order as they appeared in the input) followed by the odd numbers (also in their original order). The elements should be separated by a single space.

0