Sort Even and Odd Numbers

You are given a sequence of integers. Your task is to rearrange the sequence so that all even numbers appear before any odd numbers. The relative order among the even numbers and among the odd numbers should remain unchanged.

Formally, given an array \( A = [a_1, a_2, \dots, a_n] \), produce an array \( B \) such that:

[ B = \text{even}(A) ; \Vert ; \text{odd}(A), ]

where \( \text{even}(A) \) is the subsequence of all even numbers in \( A \) (in the same order as they appear in \( A \)) and \( \text{odd}(A) \) is the subsequence of all odd numbers in \( A \). If the input is empty or contains a single element, output it as is.

inputFormat

Input is read from standard input. A single line containing a space-separated list of integers is provided.

outputFormat

Print to standard output the rearranged list as a space-separated list where all even numbers come first (maintaining their original order) followed by all odd numbers (maintaining their original order).## sample

3 1 4 1 5 9 2 6

4 2 6 3 1 1 5 9