B. Ehab Is an Odd Persontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou're given an array a of length n. You can perform the following operation on it as many times as you want:  Pick two integers i and j (1 \le i,j \le n) such that a_i+a_j is odd, then swap a_i and a_j. What is lexicographically the smallest array you can obtain?An array x is lexicographically smaller than an array y if there exists an index i such that x_i<y_i, and x_j=y_j for all 1 \le j < i. Less formally, at the first index i in which they differ, x_i<y_iInputThe first line contains an integer n (1 \le n \le 10^5) — the number of elements in the array a.The second line contains n space-separated integers a_1, a_2, \ldots, a_{n} (1 \le a_i \le 10^9) — the elements of the array a.OutputThe only line contains n space-separated integers, the lexicographically smallest array you can obtain.ExamplesInput
3
4 1 7
Output
1 4 7 Input
2
1 1
Output
1 1 NoteIn the first example, we can swap 1 and 4 since 1+4=5, which is odd.
3
4 1 7

1 4 7 
['sortings', '*1200']