You'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_i$


-----Input-----

The 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$.


-----Output-----

The only line contains $n$ space-separated integers, the lexicographically smallest array you can obtain.


-----Examples-----
Input
3
4 1 7

Output
1 4 7 
Input
2
1 1

Output
1 1 


-----Note-----

In the first example, we can swap $1$ and $4$ since $1+4=5$, which is odd.

Difficulty: interview

Starter code:

Solutions:
import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
# print = stdout.write
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
n = input()
a = listin()
odd = 0
even = 0
for i in a:
    if i%2:
        odd+=1
    else:
        even+=1
if (even == 0 or odd == 0):
    print(*a)
else:
    a.sort()
    print(*a)

n=int(input())
l1=list(map(int,input().split()))
flag1=0
flag2=0
for item in l1:
    if item%2==0:
        flag1=1
    else :
        flag2=1
if flag1==1 and flag2==1:
    l1.sort()
print(' '.join(str(x) for x in l1))

n = int(input())
a = [int(i) for i in input().split()]
f1 = f2 = False
for i in a:
    if i % 2 == 0:
        f1 = True
    else:
        f2 = True
if f1 and f2:
    print(*sorted(a))
else:
    print(*a)

import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

ki=0
gu=0

for a in A:
    if a%2==0:
        gu=1
    else:
        ki=1

if ki==1 and gu==1:
    print(*sorted(A))
else:
    print(*A)


input()

a = list(map(int, input().split()))

if len(set([x % 2 for x in a])) == 1:
	print(*a)
else:
	print(*sorted(a))

#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue, bisect
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7
sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))
s = 0
for ai in a: s += ai%2
if s == 0 or s == n:
    print(*a)
else:
    print(*sorted(a))

from sys import stdin
n=int(stdin.readline().strip())
s=list(map(int,stdin.readline().strip().split()))
odd=False
even=False
for i in range(n):
    if s[i]%2==0:
        even=True
    else:
        odd=True
if even and odd:
    s.sort()
    print(*s)
else:
    print(*s)


n=int(input())
a=list(map(int,input().split()))
o=0
e=0
for i in range(n):
	if(a[i]%2==0):
		e+=1
	else:
		o+=1
if(o==n or e==n):
	print(*a)
else:
	a.sort()
	print(*a)

n = int(input())
*l, = map(int, input().split())
odd = False
even = False

for x in l:
	if x % 2 == 0:
		even = True
	else:
		odd = True

if odd and even:
	l.sort()
print(*l)

n=int(input())
l=list(map(int,input().split()))
if min(k%2 for k in l)==max(k%2 for k in l) :
    print(' '.join(map(str,l)))
else:
    print(' '.join(map(str,sorted(l))))


n = int(input())
s = list(map(int, input().split()))

if s[0] % 2 == 0:
    for i in range(n):
        if s[i] % 2 == 1:
            print(" ".join(map(str, sorted(s))))
            return
    print(" ".join(map(str, s)))
    return
else:
    for i in range(n):
        if s[i] % 2 == 0:
            print(" ".join(map(str, sorted(s))))
            return
    print(" ".join(map(str, s)))
    return


n = int(input())

xs = list(map(int, input().split()))
if len(set(x % 2 for x in xs)) != 1:
    xs.sort()

print(' '.join(map(str, xs)))


n=int(input())
a=list(map(int,input().split()))
odd=0
even=0
for i in a:
    if i&1:
        odd += 1
    else:
        even += 1
if odd == n or even == n:
    for i in range(len(a)):
        print(a[i],end=" ")
else:
    a=sorted(a)
    for i in range(len(a)):
        print(a[i],end=" ")
    

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def __starting_point():
    n = int(input())
    a =list(map(int,input().split()))
    eve = False
    odd = False
    for i in a:
        if i%2 == 0:
            eve = True
        else:
            odd = True
    if odd and eve:
        print(' '.join(map(str,sorted(a))))
    else:
        print(' '.join(map(str,a)))

__starting_point()

n = int(input())
a = list(map(int, input().split()))
odd = sum(x % 2 == 1 for x in a)
if odd > 0 and odd < n:
	print(*sorted(a))
else:
	print(*a)

import sys
# from bisect import bisect_left
# gcd
# from fractions import gcd
# from math import ceil, floor
# from copy import deepcopy
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# fin = open('in_1.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def __starting_point():

    # write code
    n = ii()
    a = lmi()
    if all([i % 2 == 0 for i in a]) or all([i % 2 == 1 for i in a]):
        for i in a:
            print(i, end=" ")
        print()
    else:
        a.sort()
        for i in a:
            print(i, end=" ")
        print()
    
    
__starting_point()

n = int(input())
a = list(map(int, input().split()))
md = a[0] % 2
found = False
for x in a:
	if x % 2 != md:
		found = True
if found: a.sort()
for x in a: print(str(x) + ' ', end='')

n = int(input())
a = list(map(int, input().split()))

even = 0
for i in range(n):
    if a[i] % 2 == 0:
        even += 1

if even == 0 or even == n:
    pass
else:
    a.sort()

print(" ".join(map(str, a)))


def solution():
    n = input()
    ar = list(map(int, input().split()))
    o, e = False, False
    for i in ar:
        if i % 2 == 0:
            o = True
        else:
            e = True
    if o and e:
        ar = sorted(ar)
    for a in ar:
        print(a, end=' ')


def __starting_point():
    solution()

__starting_point()



def __starting_point():
    n = int(input())
    aa = list(map(int, input().split()))
    odd, even = False, False
    for a in aa:
        if a%2==0:
            odd = True
        else:
            even = True

        if odd and even:
            break

    if odd and even:
        aa.sort()

    print(" ".join(map(str, aa)))

__starting_point()

n = int(input())
l = list(map(int, input().split()))
cnt1 = 0
cnt2 = 0
for i in range(n):
    if l[i] % 2 == 0:
        cnt1 = 1
    else:
        cnt2 = 1
if (cnt1 and cnt2):
    print(' '.join(map(str, sorted(l))))
else:
    print(' '.join(map(str,l)))


def main():
    n = int(input())
    nums = list(map(int, input().split()))
    odd = []
    even = []
    
    for ni in nums:
        if ni % 2 == 0:
            even.append(ni)
        else:
            odd.append(ni)
            
    if len(odd) == 0 or len(even) == 0:
        print(' '.join(map(str, nums)))
        return 0

    nums.sort()
    print(' '.join(map(str, nums)))
    return 0
    
main()

n = int(input().strip())
nums = list(map(int, input().strip().split()))

if all([num % 2 for num in nums]) or all([not (num % 2) for num in nums]):
    print(' '.join(map(str, nums)))
else:
    nums.sort()
    print(' '.join(map(str, nums)))


N = int(input())
X = [int(a) for a in input().split()]
A = [x for x in X if x % 2 == 0]
B = [x for x in X if x % 2 == 1]
if len(A) * len(B):
    print(*sorted(X))
else:
    print(*X)


r = int(input())
mass = [int(i) for i in input().split()]
c = False
n = False
for i in mass:
    if i % 2 == 0:
        c = True
    else:
        n = True
if c and n:
    print(*sorted(mass))
else:
    print(*mass)