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: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
def mp():
	return map(int, input().split())
n = int(input())
a = list(mp())
f = g = 0
for i in a:
	if i % 2 == 1:
		f = 1
	else:
		g = 1
if f and g:
	a.sort()
for i in a:
	print(i, end=' ')


n = int(input())
l = list(map(int, input().split()))
c = 0
for i in range(n):
	c += l[i] % 2
if c != 0 and c != n:
	l.sort()
print(*l)


n = int(input())
A = list(map(int, input().split()))
f = 0
c = 0
for i in A:
	if i % 2 != 0:
		f = 1
		c += 1
if c == n:
	print(*A)
elif f == 1:
	A.sort()
	print(*A)
else:
	print(*A)


from collections import defaultdict as dd
import math

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
n = nn()
l = lm()
good = 0
for i in range(len(l) - 1):
	if not l[i] % 2 == l[i + 1] % 2:
		good = 1
if good == 0:
	print(*l)
else:
	l.sort()
	print(*l)


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()


n = int(input())
a1 = list(map(int, input().split()))
(a, b) = (0, 0)
for i in a1:
	if i % 2 == 0:
		a += 1
	else:
		b += 1
if a != 0 and b != 0:
	a1.sort()
	print(*a1)
else:
	print(*a1)


import sys
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
readl = lambda : list(map(int, sys.stdin.readline().split()))
readt = lambda : tuple(map(int, sys.stdin.readline().split()))
read = lambda : sys.stdin.readline().rstrip()
readi = lambda : int(read())
readmi = lambda : map(int, sys.stdin.readline().split())
readms = lambda : map(str, sys.stdin.readline().split())
n = readi()
m = readl()
gu_count = 0
ki_count = 0
for (i, v) in enumerate(m):
	if v % 2 == 0:
		gu_count += 1
	else:
		ki_count += 1
if gu_count >= 1 and ki_count >= 1:
	m.sort()
for i in m:
	print(i, end=' ')


n = int(input())
a = list(map(int, input().split()))
if len([x for x in a if x % 2 == 0]) in (0, n):
	print(*[x for x in a])
else:
	print(*[x for x in sorted(a)])


import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())
n = val()
a = li()
(possible1, possible2) = [False] * 2
for i in a:
	if i & 1:
		possible1 = True
	else:
		possible2 = True
if possible1 and possible2:
	a.sort()
print(*a)


n = int(input())
a = list(map(int, input().split()))
flag0 = 0
flag1 = 0
for i in a:
	if i & 1 == 1:
		flag1 = 1
	if i & 1 == 0:
		flag0 = 1
if flag0 == 1 and flag1 == 1:
	a.sort()
for i in a:
	print(i, end=' ')


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)


n = int(input())
a = list(map(int, input().split()))
c1 = 0
j = 0
c2 = 0
while not (c1 > 0 and c2 > 0) and j < n:
	if a[j] % 2 != 0:
		c1 += 1
	else:
		c2 += 1
	j += 1
if c1 == 0 or c2 == 0:
	print(*a)
else:
	a.sort()
	print(*a)


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)))


import sys
sys.setrecursionlimit(int(10000000.0))
R = lambda : map(int, input().split())

def main():
	((n,), l) = (R(), list(R()))
	if any((x % 2 == 0 for x in l)) and any((x % 2 == 1 for x in l)):
		l.sort()
	print(' '.join(map(str, l)))
	return
while 1:
	try:
		main()
	except EOFError:
		break


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)))


n = int(input())
arr = list(map(int, input().split()))
allEven = True
for i in arr:
	if i % 2 != 0:
		allEven = False
		break
allOdd = True
for i in arr:
	if i % 2 == 0:
		allOdd = False
		break
if allOdd is False and allEven is False:
	arr.sort()
	for i in arr:
		print(i, end=' ')
else:
	for i in arr:
		print(i, end=' ')


import sys
import os
from io import BytesIO, IOBase

def cel(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return defaultdict(int)

def ddl():
	return defaultdict(list)

def ddd():
	return defaultdict(defaultdict(int))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict
for _ in range(1):
	n = ii()
	a = li()
	cnt = 0
	for i in range(n):
		if a[i] & 1:
			cnt += 1
	if cnt == n or cnt == 0:
		print(*a)
	else:
		print(*sorted(a))


n = int(input())
l = list(map(int, input().split()))
od = 0
for el in l:
	od += el & 1
if od > 0 and n - od != 0:
	l.sort()
print(*l)


n = int(input())
l = [int(x) for x in input().split(' ')]
(odd, even) = (0, 0)
for i in l:
	if i % 2:
		odd += 1
	else:
		even += 1
if odd and even:
	l.sort()
print(*l)


n = int(input())
a = list(map(int, input().split()))
b = list()
c = list()
for i in range(n):
	if a[i] % 2 == 0:
		b.append(a[i])
	else:
		c.append(a[i])
if len(b) != 0 and len(c) != 0:
	b.sort()
	c.sort()
	i = 0
	j = 0
	while 1:
		if i == len(b) or j == len(c):
			break
		if b[i] < c[j]:
			print(b[i], end=' ')
			i += 1
		else:
			print(c[j], end=' ')
			j += 1
	if i != len(b):
		for m in range(i, len(b)):
			print(b[m], end=' ')
	else:
		for m in range(j, len(c)):
			print(c[m], end=' ')
else:
	for i in range(n):
		print(a[i], end=' ')


n = int(input())
ls = list(map(int, input().split()))
b = [0, 0]
for i in range(n):
	b[ls[i] % 2] = 1
if b[0] and b[1]:
	ls.sort()
for j in range(n):
	print(ls[j], end=' ')


n = int(input())
a = [int(x) for x in input().split()]
ans = [int(x) % 2 for x in a]
if 1 in ans and 0 in ans:
	print(*sorted(a))
else:
	print(*a)


n = int(input())
arr = list(map(int, input().split()))
max_val = 10 ** 10
min_even = min_odd = max_val
for i in arr:
	if i % 2 == 0 and i < min_even:
		min_even = i
	if i % 2 != 0 and i < min_odd:
		min_odd = i
if min_odd == max_val or min_even == max_val:
	for i in arr:
		print(i, end=' ')
	print()
else:
	arr.sort()
	for i in arr:
		print(i, end=' ')
	print()


n = int(input())
arr = list(map(int, input().split()))
(o, e) = (0, 0)
for u in arr:
	if u % 2 != 0:
		o += 1
	else:
		e += 1
	if o and e:
		arr.sort()
		print(*arr)
		exit()
print(*arr)


n = int(input())
arr = list(map(int, input().split()))
parityDiff = False
for i in range(len(arr) - 1):
	if not arr[i] % 2 == arr[i + 1] % 2:
		parityDiff = True
		break
if parityDiff:
	arr.sort()
for e in arr:
	print(e, end=' ')
print()


n = int(input())
a = list(map(int, input().split()))
odd = 0
even = 0
for i in a:
	if i % 2 == 0:
		even = 1
	if i % 2 != 0:
		odd = 1
	if even == 1 and odd == 1:
		break
if even == 1 and odd == 1:
	a.sort()
	for i in a:
		print(i, end=' ')
else:
	for i in a:
		print(i, end=' ')


N = int(input())
sk = [int(x) for x in input().split()]
even = 0
odd = 0
for i in sk:
	if i & 1:
		odd += 1
	else:
		even += 1
if odd and even:
	sk.sort()
for i in sk:
	print(i, end=' ')


def lexicographically(n, l):
	for i in l:
		if (i + l[0]) % 2 == 1:
			l.sort()
			break
	print(*l)
n = int(input())
l = list(map(int, input().split()))
lexicographically(n, l)


n = int(input())
s = input().split()
a = []
odd = 0
for x in s:
	e = int(x)
	a.append(e)
	if e % 2 == 1:
		odd = odd + 1
if odd > 0 and n - odd > 0:
	a.sort()
	for x in a:
		print(x, end=' ')
else:
	for x in a:
		print(x, end=' ')


def solve(arr):
	val = arr[0] % 2
	for i in arr:
		if i % 2 != val:
			arr.sort()
			return arr
	return arr

def main():
	t = int(input().strip())
	lineinp = input().strip()
	arr = list(map(int, lineinp.split()))
	gp = solve(arr)
	for i in gp:
		print('{} '.format(i), end='')
main()


n = int(input())
a = list(map(int, input().split()))
if any((e % 2 != a[0] % 2 for e in a)):
	a.sort()
print(*a)


n = eval(input())
a = list(map(int, input().split()))
odd = False
even = False
for i in range(n):
	if a[i] & 1:
		odd = True
	else:
		even = True
if odd & even:
	a.sort()
for x in a:
	print(x, end=' ')


n = int(input().strip())
arr = list(map(int, input().strip().split()))
(odds, evens) = (0, 0)
for ele in arr:
	if ele % 2:
		odds += 1
	else:
		evens += 1
if odds == 0 or evens == 0:
	print(*arr)
else:
	arr.sort()
	print(*arr)


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())
a = list(map(int, input().split()))
c = False
nc = False
for i in a:
	if i % 2:
		nc = True
	else:
		c = True
if c & nc:
	a.sort()
	for i in a:
		print(i, end=' ')
else:
	for i in a:
		print(i, end=' ')


n = int(input())
a = [int(i) for i in input().split()]
vis = 0
for i in a:
	if i & 1:
		vis += 1
if vis and vis < n:
	a.sort()
for i in a:
	print(i, end=' ')


x = int(input())
y = [int(q) for q in input().split()]
odd = 0
even = 0
for q in y:
	if q % 2 == 0:
		even = 1
	else:
		odd = 1
if even == 1 and odd == 1:
	y = sorted(y)
print(*y)


input()
a = list(map(int, input().split()))
if len(set([x % 2 for x in a])) == 1:
	print(*a)
else:
	print(*sorted(a))


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='')


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
c = [False, False]
for i in range(n):
	c[a[i] % 2] = True
	if c.count(True) == 2:
		break
if c.count(True) == 2:
	a.sort()
for i in range(n):
	print(a[i], end=' ')


n = int(input())
s = list(map(int, input().split()))
s1 = set(map(lambda x: x % 2, s))
if len(s1) == 2:
	print(' '.join(map(str, sorted(s))))
else:
	print(' '.join(map(str, s)))


import sys, math

def read_int():
	return int(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_string():
	return sys.stdin.readline().strip()

def read_string_list(delim=' '):
	return sys.stdin.readline().strip().split(delim)

def print_int_list(l):
	print(' '.join(map(str, l)))
n = read_int()
arr = read_int_list()
if_all_even = 1
for i in range(n):
	if arr[i] & 1 == 1:
		if_all_even = 0
		break
if if_all_even:
	print_int_list(arr)
	sys.exit()
if_all_odd = 1
for i in range(n):
	if arr[i] & 1 == 0:
		if_all_odd = 0
		break
if if_all_odd:
	print_int_list(arr)
	sys.exit()
arr.sort()
print_int_list(arr)


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)


n = int(input())
arr = list(map(int, input().split()))
i = 0 if arr[0] % 2 == 0 else -1
for j in range(1, n):
	if arr[j] % 2 == 0 and i == -1 or (i == 0 and arr[j] % 2):
		i = 2
		break
if i == 2:
	arr.sort()
print(' '.join(map(str, arr)))


n = int(input())
arr = list(map(int, input().split()))
ec = 0
oc = 0
for i in range(len(arr)):
	if arr[i] % 2 != 0:
		oc += 1
	else:
		ec += 1
if oc == 0 or ec == 0:
	print(*arr, sep=' ')
else:
	print(*sorted(arr), sep=' ')


n = int(input())
a = list(map(int, input().split()))
ex = [0, 0]
for i in range(n):
	ex[a[i] % 2] = 1
if ex[0] & ex[1]:
	a.sort()
print(*a)


(N, X) = (int(input()), list(map(int, input().split())))
if len(list(filter(lambda x: x % 2 == 1, X))) not in [0, N]:
	print(*sorted(X))
else:
	print(*X)


t = int(input())
a = input().split(' ')
l = list(map(int, a))
count = 0
for i in l:
	if i % 2 == 0:
		count = count + 1
if count == 0 or count == t:
	for j in l:
		print(j, end=' ')
else:
	l.sort()
	for k in l:
		print(k, end=' ')


a = int(input())
b = list(map(int, input().split()))
c = sum((i & 1 for i in b))
if 0 < c < a:
	print(*sorted(b))
else:
	print(*b)


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from heapq import heappush as hpush
from heapq import heappop as hpop
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
n = ri(1)
a = ri()
su = sum([i % 2 for i in a])
if su == 0 or su == n:
	print(*a)
else:
	a.sort()
	print(*a)


n = int(input())
A = list(map(int, input().split()))
o = 0
for i in A:
	if i & 1:
		o += 1
if o == n or o == 0:
	print(*A)
else:
	A.sort()
	print(*A)


n = int(input())
arr = list(map(int, input().split(' ')))
even = 0
for i in arr:
	if i % 2 == 0:
		even += 1
if even == 0 or even == n:
	pass
else:
	arr.sort()
print(*arr)


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
input()
a = list(map(int, input().split()))
if len(set([x % 2 for x in a])) == 1:
	print(*a)
else:
	print(*sorted(a))


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
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)


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)


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)


import sys, math, string
input = sys.stdin.readline
from collections import deque
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
n = int(input())
a = L()
od = 0
ev = 0
for i in range(n):
	if a[i] % 2 == 0:
		ev += 1
	else:
		od += 1
if od == 0 or ev == 0:
	print(*a)
else:
	a.sort()
	print(*a)


n = input()
l = list(map(int, input().split(' ')))
(odd, even) = (0, 0)
for s in l:
	if s % 2:
		odd += 1
	else:
		even += 1
if odd and even:
	l = sorted(l)
print(*l)


def printf(a):
	for num in a:
		print(num, end=' ')
n = int(input())
a = list(map(int, input().split()))
count = 0
for num in a:
	if num % 2 == 0:
		count += 1
if count != 0 and count != n:
	a.sort()
printf(a)


n = int(input())
l = list(map(int, input().split()))
flag = 0
odd = False
even = False
for i in range(n):
	if l[i] % 2 == 0:
		even = True
	else:
		odd = True
s = ''
if even and odd:
	l.sort()
	for i in range(n):
		s += str(l[i]) + ' '
else:
	for i in range(n):
		s += str(l[i]) + ' '
print(s[:-1])


import os
import operator
import sys
import bisect
import _operator
from _collections import defaultdict
from io import BytesIO, IOBase

def inar():
	return [int(k) for k in input().split()]

def power(x, p, m):
	res = 1
	while p:
		if p & 1:
			res = res * x % m
		x = x * x % m
		p >>= 1
	return res

def main():
	n = int(input())
	arr = inar()
	odd = 0
	even = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd > 0 and even > 0:
		arr.sort()
		print(*arr)
	else:
		print(*arr)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys, math, queue, bisect
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, stdout
from collections import *
from math import gcd, floor, ceil

def st():
	return list(stdin.readline().strip())

def li():
	return list(map(int, stdin.readline().split()))

def mp():
	return map(int, stdin.readline().split())

def inp():
	return int(stdin.readline())

def pr(n):
	return stdout.write(str(n) + '\n')
mod = 1000000007
INF = float('inf')

def solve():
	n = inp()
	l = li()
	(even, odd) = ([], [])
	for i in range(n):
		if l[i] & 1:
			odd.append(i)
		else:
			even.append(i)
	if even and odd:
		l.sort()
	print(*l)
for _ in range(1):
	solve()


def isvalid(li):
	for i in li:
		if (i - li[0]) % 2:
			return 1
	return 0
n = int(input())
l = input().split()
li = [int(i) for i in l]
if isvalid(li):
	li.sort()
	for i in li:
		print(i, end=' ')
	print()
else:
	for i in li:
		print(i, end=' ')
	print()


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=' ')


n = int(input())
ar = list(map(int, input().split()))[:n]
b = []
for i in range(n):
	b.append(ar[i] % 2)
s = set(b)
if len(s) == 1:
	print(*ar)
else:
	ar.sort()
	print(*ar)


n = int(input())
t = list(map(int, input().split()))
odd = 0
even = 0
for x in t:
	if x % 2 == 0:
		even += 1
	else:
		odd += 1
if even == 0 or odd == 0:
	print(' '.join((str(z) for z in t)))
else:
	t = sorted(t)
	print(' '.join((str(z) for z in t)))


n = int(input())
lis = list(map(int, input().split()))
(a1, a2) = ([True if i % 2 == 0 else False for i in lis], [True if i % 2 != 0 else False for i in lis])
if all(a1) or all(a2):
	for p in lis:
		print(p, end=' ')
else:
	for d in sorted(lis):
		print(d, end=' ')


def strange(lst):
	(even, odd) = (False, False)
	for elem in lst:
		if elem % 2 == 0:
			even = True
		else:
			odd = True
	if even and odd:
		lst.sort()
	return lst
n = int(input())
a = [int(j) for j in input().split()]
print(*strange(a))


n = int(input())
numbers = list(map(int, input().split(' ')))
has_even = False
has_odd = False
for num in numbers:
	has_even |= (num + 1) % 2
	has_odd |= num % 2
if not has_even or not has_odd:
	print(*numbers, sep=' ')
	exit(0)
print(*sorted(numbers), sep=' ')


n = int(input())
l = list(map(int, input().split()))
(odd, even) = (0, 0)
for i in l:
	if i % 2 == 0:
		even += 1
	else:
		odd += 1
if odd + even != max(odd, even):
	print(*sorted(l))
else:
	print(*l)


input()
a = [*map(int, input().split())]
if any(((x - a[0]) % 2 for x in a)):
	a.sort()
print(*a)


from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm, accumulate
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return input()

def num():
	return int(input())

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def pmat2(A):
	for ele in A:
		for j in ele:
			print(j, end='')
		print()

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
n = int(data())
a = L()
ans = a[0]
flag = False
for i in range(1, n):
	if (ans + a[i]) % 2 == 1:
		flag = True
		break
if flag:
	print(*sorted(a))
else:
	print(*a)
endtime = time.time()


n = int(input())
arr = list(map(int, input().split()))
f1 = False
f2 = False
for i in arr:
	if f1 and f2:
		break
	if i % 2:
		f1 = True
	else:
		f2 = True
if f1 and f2:
	print(*sorted(arr))
else:
	print(*arr)


from sys import stdin, stdout
input = stdin.readline
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
(n, a) = (rint(), rints())
if sum([i & 1 == 0 for i in a]) == n or sum([i & 1 for i in a]) == n:
	print(*a)
else:
	print(*sorted(a))


x = int(input())
n = list(map(int, input().split(' ')))
odd = even = 0
for num in n:
	if num & 1:
		odd += 1
	else:
		even += 1
if n == 1:
	print(*n)
if odd >= 1 and even >= 1:
	n = sorted(n)
print(*n)


n = int(input())
a = list(map(int, input().split()))
(c, d, ind) = (False, False, 0)
while (not c or not d) and ind < n:
	if a[ind] % 2 == 0:
		d = True
	else:
		c = True
	ind += 1
if c and d:
	print(' '.join((str(e) for e in sorted(a))))
else:
	print(' '.join((str(e) for e in a)))


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


import collections
n = int(input())
a = [int(i) for i in input().split()]
flag1 = 0
for i in range(0, n):
	if a[i] % 2 != 0:
		flag1 = 1
		break
flag2 = 0
for i in range(0, n):
	if a[i] % 2 == 0:
		flag2 = 1
		break
if flag1 == 0 or flag2 == 0:
	print(*a, sep=' ')
else:
	a.sort()
	print(*a, sep=' ')


import sys
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())

def __starting_point():
	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 = [int(i) for i in input().split()]
k1 = 0
k2 = 0
i = 0
while k1 == 0 or k2 == 0:
	if i >= n:
		break
	if a[i] % 2 == 1:
		k1 += 1
	else:
		k2 += 1
	i += 1
if k1 * k2 != 0:
	a.sort()
	print(*a)
else:
	print(*a)


n = int(input())
l = list(map(int, input().strip().split(' ')))
s = 0
for i in range(n):
	s += l[i] % 2
if s == 0 or s == n:
	print(*l)
else:
	l.sort()
	print(*l)


from collections import deque
n = int(input())
a = [int(i) for i in input().split()]
k = a[0] % 2
aa = False
for i in range(1, n):
	if k == a[i] % 2:
		aa = False
	else:
		aa = True
		break
if aa:
	ans = sorted(a)
else:
	ans = a
print(*ans)


from sys import stdin, stdout
import math, sys
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import bisect as bi
import heapq

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_right(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		n = I()
		l = list(In())
		odd = 0
		for x in range(n):
			if l[x] & 1 == 1:
				odd += 1
		if odd == n or odd == 0:
			print(*l)
		else:
			l.sort()
			print(*l)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


n = int(input())
a = list(map(int, input().split()))
nbp = 0
nbimp = 0
for x in a:
	if x % 2 == 0:
		nbp += 1
	else:
		nbimp += 1
if nbp > 0 and nbimp > 0:
	a.sort()
print(*a)


import io
import os
import sys
from atexit import register
import random
import math
import itertools
from collections import deque
DEBUG = False
STRESSTEST = False
if not DEBUG:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
tokens = []
tokens_next = 0

def nextStr():
	global tokens, tokens_next
	while tokens_next >= len(tokens):
		tokens = input().split()
		tokens_next = 0
	tokens_next += 1
	if type(tokens[tokens_next - 1]) == str:
		return tokens[tokens_next - 1]
	return tokens[tokens_next - 1].decode()

def nextInt():
	return int(nextStr())

def nextIntArr(n):
	return [nextInt() for i in range(n)]

def print(*argv, end='\n'):
	for arg in argv:
		sys.stdout.write((str(arg) + ' ').encode())
	sys.stdout.write(end.encode())

def genTestCase():
	n = random.randint(1, 10)
	return [random.randint(1, 100) for _ in range(n)]

def bruteforce(a):
	res = a
	q = deque()
	q.append(a)
	visited = set()
	while len(q) > 0:
		cur = q.popleft()
		if tuple(cur) in visited:
			continue
		visited.add(tuple(cur))
		res = min(res, cur)
		for i in range(len(cur)):
			for j in range(i + 1, len(cur)):
				if (cur[i] + cur[j]) % 2 == 1:
					t = cur[:]
					(t[i], t[j]) = (t[j], t[i])
					q.append(t)
	return ' '.join(map(str, res))

def doStressTest():
	while True:
		curTest = genTestCase()
		mySoln = solve(curTest)
		bruteforceSoln = bruteforce(curTest)
		if mySoln != bruteforceSoln:
			print('### Found case ###')
			print(curTest)
			print(f'{mySoln} should have been: {bruteforceSoln}')
			return

def solve(a):
	hasEven = any((i % 2 == 0 for i in a))
	hasOdd = any((i % 2 == 1 for i in a))
	if hasEven and hasOdd:
		a = sorted(a)
	return ' '.join(map(str, a))
if not DEBUG and STRESSTEST:
	raise Exception('Wrong flags!')
if STRESSTEST:
	doStressTest()
else:
	a = nextIntArr(nextInt())
	res = solve(a)
	print(res)
sys.stdout.flush()


from sys import stdin, stdout
n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
odd = False
even = False
for i in range(len(arr)):
	if arr[i] % 2 == 0:
		even = True
	if arr[i] % 2 == 1:
		odd = True
if odd and even:
	arr.sort()
	for i in range(len(arr)):
		stdout.write(str(arr[i]) + ' ')
else:
	for i in range(len(arr)):
		stdout.write(str(arr[i]) + ' ')


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()


import sys
input = sys.stdin.readline
from collections import *
n = int(input())
a = list(map(int, input().split()))
flag = True
for i in range(n):
	if a[i] % 2 != a[0] % 2:
		flag = False
if flag:
	print(*a)
	exit()
a.sort()
print(*a)


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)))


input()
inp_arr = list(map(int, input().split()))
even = False
odd = False
for i in inp_arr:
	if even and odd:
		break
	if i % 2 == 0:
		even = True
	else:
		odd = True
if even and odd:
	inp_arr.sort()
print(*inp_arr)


n = int(input())
list_val = [int(val) for val in input().split(' ')]
odd = False
even = False
for val in list_val:
	if val % 2 != 0:
		odd = True
		break
for val in list_val:
	if val % 2 == 0:
		even = True
		break
if odd and even:
	list_val = sorted(list_val)
	print(' '.join((str(val) for val in list_val)))
else:
	print(' '.join((str(val) for val in list_val)))


input()
a = list(map(int, input().split()))
e = o = 0
for i in a:
	if i & 1:
		o = 1
	else:
		e = 1
	if e and o:
		a.sort()
		break
print(*a)


n = int(input())
num = [int(i) for i in input().split(' ')]
odd = 0
even = 0
for i in num:
	if even and odd:
		break
	if i % 2 == 0:
		even = 1
	else:
		odd = 1
if even and odd:
	num = sorted(num)
s = ''
for i in range(0, len(num)):
	s += str(num[i]) + ' '
print(s)


n = int(input())
from collections import Counter
arr = [int(i) for i in input().split()]
us = Counter()
o = 0
for i in arr:
	us[i] = i
	o += i % 2 == 0
if o != n and o != 0:
	arr.sort()
print(*arr)


from math import *
n = int(input())
l = list(map(int, input().split()))
a = [0, 0]
for i in l:
	a[i % 2] += 1
if a[0] == 0 or a[1] == 0:
	for i in l:
		print(i, end=' ')
	print()
else:
	l.sort()
	for i in l:
		print(i, end=' ')
	print()


n = int(input())
a = list(map(int, input().rstrip().split()))
oc = len(list(filter(lambda x: x % 2 != 0, a)))
ec = len(list(filter(lambda x: x % 2 == 0, a)))
if ec == 0 or oc == 0:
	print(*a)
else:
	a.sort()
	print(*a)


n = int(input())
a = [int(o) for o in input().split()]
(ec, oc) = (0, 0)
for i in range(n):
	if a[i] % 2 == 0:
		ec += 1
	else:
		oc += 1
if ec > 0 and oc > 0:
	a = sorted(a)
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())
s = list(map(int, input().split()))
s1 = sorted(s)
i = 0
j = 0
for x in s:
	if x % 2:
		i += 1
	else:
		j += 1
if i == n or j == n:
	print(*s, sep=' ')
else:
	print(*s1, sep=' ')


n = int(input())
a = list(map(int, input().split()))
(c, d, ind) = (False, False, 0)
while (not c or not d) and ind < n:
	if a[ind] % 2 == 0:
		d = True
	else:
		c = True
	ind += 1
if c and d:
	print(*sorted(a))
else:
	print(*a)


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


n = int(input())
l = list(map(int, input().split(' ')))
s = 0
for i in l:
	s += i & 1
if s == 0 or s == n:
	print(*l)
else:
	l.sort()
	print(*l)


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


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
arr = lmp()
c1 = 0
for i in arr:
	c1 += i % 2
if c1 in [0, n]:
	print(*arr)
else:
	print(*sorted(arr))


n = input()
n = int(n)
arr = list(map(int, input().split()))
x = 0
for e in arr:
	if e % 2 == 0:
		x += 1
if x == 0 or x == n:
	for e in arr:
		print(e, end=' ')
else:
	arr.sort()
	for e in arr:
		print(e, end=' ')


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


n = int(input())
l = list(map(int, input().split()))
c = 0
for i in range(n):
	c += l[i] % 2
if c == 0 or c == n:
	print(*l)
else:
	print(*sorted(l))


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)


from sys import stdin
import heapq
import collections

def all_odd(arr, n):
	for i in arr:
		if i % 2 == 1:
			continue
		else:
			return False
	return True

def all_even(arr, n):
	for i in arr:
		if i % 2 == 0:
			continue
		else:
			return False
	return True
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
if all_odd(arr, n) or all_even(arr, n):
	print(*arr)
else:
	arr.sort()
	print(*arr)


size = int(input())
a = list(map(int, 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 os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = array()
odd = [i for i in a if i % 2]
if 0 < len(odd) < n:
	print(*sorted(a))
else:
	print(*a)


a = [0, 0]
x = int(input())
m = list(map(int, input().split()))
for i in m:
	a[i % 2] = 1
	if a[0] and a[1]:
		m = sorted(m)
		break
for i in range(x):
	print(m[i], end=' ')


n = int(input())
arr = list(map(int, input().split()))
(a, b) = (0, 0)
for i in arr:
	if i % 2:
		a += 1
	else:
		b += 1
if a != 0 and b != 0:
	print(*sorted(arr))
else:
	print(*arr)


n = int(input())
arr = [int(x) for x in input().split()]
(odd, even) = ([], [])
for i in range(n):
	if arr[i] % 2 == 0:
		even.append([arr[i], i])
	else:
		odd.append([arr[i], i])
if len(odd) > 0 and len(even) > 0 or n == 1:
	for x in sorted(arr):
		print(x, end=' ')
else:
	for x in arr:
		print(x, end=' ')


n = int(input())
m = list(map(int, input().split()))
odd = [i for i in m if i % 2]
even = [i for i in m if not i % 2]
if odd and even:
	print(' '.join(map(str, sorted(m))))
else:
	print(' '.join(map(str, m)))


import sys, math, bisect
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import string
n = int(input())
arr = list(map(int, input().split()))
parity = [1 if arr[i] % 2 else 0 for i in range(n)]
if sum(parity) != 0 and sum(parity) < n:
	arr.sort()
	print(*arr)
else:
	print(*arr)


n = int(input())
a = list(map(int, input().split()))
for i in a:
	if i % 2 != a[0] % 2:
		print(*sorted(a))
		exit()
else:
	print(*a)


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)


n = int(input())
a = list(map(int, input().split()))
odd = []
even = []
b = sorted(a)
for i in range(len(a)):
	if a[i] % 2 == 0:
		even.append(a[i])
	else:
		odd.append(a[i])
if len(odd) == n or len(even) == n:
	for i in range(len(a)):
		print(a[i], end=' ')
else:
	for i in range(len(b)):
		print(b[i], end=' ')


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 = list(map(int, input().split()))
rem = []
for i in A:
	rem.append(i % 2)
if max(rem) == min(rem):
	print(*A)
else:
	A.sort()
	print(*A)


import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
z = int(input())
arr = get_array()
count_odd = 0
count_even = 0
for i in arr:
	if i & 1:
		count_odd += 1
	else:
		count_even += 1
if count_odd == 0 and count_even > 0 or (count_even == 0 and count_odd > 0):
	print(*arr, sep=' ')
else:
	arr.sort()
	print(*arr, sep=' ')


import sys
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve(n, arr):
	(o, e) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if o == 0 or e == 0:
		print(*arr)
	else:
		print(*sorted(arr))
n = int(input())
arr = int_arr()
solve(n, arr)


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)))


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())
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


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()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

def nninp():
	return map(int, input().split())

def llinp():
	return list(map(int, input().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
from collections import OrderedDict
n = int(input())
a = list(map(int, input().split()))
odd = even = 0
for i in range(n):
	if a[i] % 2 == 0:
		even += 1
	else:
		odd += 1
if odd == 0 or even == 0:
	print(*a)
else:
	a.sort()
	print(*a)


n = int(input())
a = [int(x) for x in input().strip().split()]
mx = 0
c_e = 0
c_o = 0
for i in range(n):
	e = a[i]
	if e % 2 == 1:
		c_o = 1
	else:
		c_e = 1
if c_o == 1 and c_e == 1:
	a.sort()
print(*a)


n = int(input())
y = list(map(int, input().split()))
b = 0
c = 0
for x in y:
	if x % 2 == 0:
		b += 1
	else:
		c += 1
if b == len(y):
	for x in y:
		print(x, end=' ')
elif c == len(y):
	for x in y:
		print(x, end=' ')
else:
	y.sort()
	for x in y:
		print(x, end=' ')


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 10 ** 9 + 7
n = I()
a = list(R())
x = [i % 2 for i in a]
if 1 in x and 0 in x:
	print(*sorted(a))
else:
	print(*a)


n = int(input())
lst = list(map(int, input().split()))
(k1, k2) = (0, 0)
for (i, x) in enumerate(lst):
	if x % 2 == 0:
		k1 = 1
	if x % 2 == 1:
		k2 = 1
	if k1 == 1 and k2 == 1:
		break
if k1 == 1 and k2 == 1:
	lst.sort()
	print(*lst)
else:
	print(*lst)


n = int(input())
a = [int(x) for x in input().split()]
counter = 0
for item in a:
	if item % 2 == 0:
		counter += 1
if counter == 0 or counter == n:
	print(*a)
else:
	print(*sorted(a))


n = int(input())
a = list(map(int, input().split()))
(s, t) = (0, 0)
for i in range(n):
	if a[i] % 2 == 0:
		s = s + 1
	else:
		t = t + 1
if s == 0 or t == 0:
	for k in a:
		print(k, end=' ')
else:
	a.sort()
	for k in a:
		print(k, end=' ')


n = int(input())
a = list(map(int, input().split()))
cn = 0
for ta in a:
	if ta % 2:
		cn += 1
if cn == 0 or cn == n:
	print(*a)
else:
	a.sort()
	print(*a)


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


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)))