A deadly virus is sweeping across the globe! You are part of an elite group of programmers tasked with tracking the spread of the virus. You have been given the timestamps of people entering and exiting a room. Now your job is to determine how the virus will spread. Hurry up, time is of the essence!

There are $N$ people in this scenario, numbered from $1$ to $N$. Every day, the $i$th person enters and exits the room at time $s_ i$ and $t_ i$ respectively. At the beginning of the $1$st day, there are $C$ people infected with the virus, whose indices will be given in the input.

When an infected person comes into contact with an uninfected person, the uninfected person will become infected at the start of the next day. Hence, they can only start spreading the infection from the next day onward. An infected person will always remain infected.

Two people are in contact with each other if they are in the room at the same time. This includes cases where one person leaves and another person enters at the exact same time. Also, if a person enters and exits the room at the same time ($s_ i$ = $t_ i$), they are considered to be in contact with everyone in the room at that time. Due to safe-distancing requirements, no more than $50$ people can be in the room at one time.

Your job is to print the indices of the people who will be infected after $D$ days. This includes people who came into contact with an infected person on the $D$th day but will only become infected at the start of the $D+1$th day.

Given below are the visualizations for sample inputs $1$ and $2$.

Note: In sample $2$, person $2$ and $4$ will get infected after day $1$. They can only spread the infection to person $3$ and $5$ on day $2$. For $D = 1$, the infected people are $1$, $2$, $4$. If $D$ had been $2$, person $3$ and $5$ would have also been infected.

-----Input-----
The first line contains two integers, $1 \le N \le 20000$, and $1 \le D \le 50000$, the number of people and number of days respectively.

The second line contains an integer $1 \le C \le N$, the initial number of infected people, followed by $C$ integers, the indices of the infected people. Indices are from $1$ to $N$.

The next $N$ lines describe the entry and exit times of the $N$ people, in order from $1$ to $N$. Each line contains two integers, $s_ i$ and $t_ i$, the entry and exit time respectively. $0 \le s_ i \le t_ i \le 10^9$.

-----Output-----
Print a list of indices of people infected after $D$ days, in ascending order. The indices should be all on one line, separated by a single space.

-----Subtasks-----
 - ($40$ Points): $N \le 5000$. $D = 1$, $C = 1$. Initially, only the person with index $1$ is infected.
 - ($30$ Points): $N \le 5000$, $D \le 5$.
 - ($20$ Points): $N \le 5000$.
 - ($10$ Points): No additional constraint.

-----Examples-----
Sample Input 1:
9 1
1 1
5 10
1 3
11 14
5 5
10 10
3 6
6 12
7 7
4 11
Sample Output 1:
1 4 5 6 7 8 9

Sample Input 2:
5 1
1 1
3 3
2 3
1 2
3 4
4 5
Sample Output 2:
1 2 4

Sample Input 3:
5 1
1 1
3 3
3 3
4 4
4 4
5 5
Sample Output 3:
1 2

Difficulty: HARD

Starter code:

Solutions:
n=int(input())
a=input().split()
ones=a.count("1")
twos=n-ones
if ones==0 or twos==0:
	print(" ".join(a))
else:
	print("2 1"+" 2"*(twos-1)+" 1"*(ones-1))


import sys
input = sys.stdin.readline

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

from collections import Counter
counter=Counter(A)

if counter[1]==0 or counter[2]==0:
	print(*A)
	return

if counter[1]==1:
	ANS=[2,1]
	ANS+=[2]*(counter[2]-1)
	print(*ANS)
	return

if counter[1]%2==0:
	ANS=[2,1]
	counter[2]-=1
	counter[1]-=1

	ANS+=[1]*(counter[1]-1)
	ANS+=[2]*counter[2]
	ANS+=[1]

	print(*ANS)
	return

if counter[1]%2==1:
	ANS=[2,1]
	counter[2]-=1
	counter[1]-=1

	ANS+=[1]*counter[1]
	ANS+=[2]*counter[2]

	print(*ANS)
	return


	


from collections import Counter

n = int(input())
c = Counter(list(map(int, input().split())))

if c[1] == 0:
	print('2 ' * c[2])
elif c[2] == 0:
	print('1 ' * c[1])
else:
	print('2 1 ' + '2 ' * (c[2] - 1) + '1 ' * (c[1] - 1))


import math
#import random
#import time
r = lambda: int(input())
ra = lambda: [*list(map(int, input().split()))]

def s(a):
	if a<=1: return False
	else:
		for i in range(2, int(math.sqrt(a))+1):
			if a%i==0:
				return False
		return True

n = r()
a = ra()
#a = [random.choice([1,2]) for i in range(n)]
#ti = time.time()
o = [i for i in a if i == 1]
o = len(o)
t = len(a)-o
b = 0
an = []
while o!=0 and t!=0:
	if s(b+1):
		an+=[1]
		o-=1
		b+=1
	else:
		an+=[2]
		t-=1
		b+=2
if o==0:
	a = [2]*t
else:
	a = [1]*o
an+=a
print(*an)
#print(time.time()-ti)


N = int(input())
A = [int(a) for a in input().split()]

n1 = A.count(1)
n2 = A.count(2)

if n1*n2==0:
	print(*A)
else:
	s1 = (n1-1)//2*2
	ANS = [2,1]+[1]*s1+[2]*(n2-1)+[1]*(n1-1-s1)
	print(*ANS)


N = int(input())
A = [int(a) for a in input().split()]

n1 = A.count(1)
n2 = A.count(2)

if n1*n2 == 0:
	print(*A)
else:
	print(*([2,1]+[2]*(n2-1)+[1]*(n1-1)))



def sieve(n):
	n += 1
	
	prime = [True] * n
	for i in range(2, n):
		if i * i > n:
			break
		if prime[i]:
			for j in range(i * i, n, i):
				prime[j] = False

	res = [0]
	for i in range(2, n):
		if prime[i]:
			res.append(i)
	
	return res

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

cnt = [0] * 3
for i in a:
	cnt[i] += 1

primes = sieve(sum(a) + 1)

ans = []
for i in range(1, len(primes)):
	dist = primes[i] - primes[i - 1]

	take_two = min(dist // 2, cnt[2])
	take_one = min(dist - 2 * take_two, cnt[1])

	cnt[2] -= take_two
	cnt[1] -= take_one

	ans.extend([2] * take_two)    
	ans.extend([1] * take_one)

ans.extend([2] * cnt[2])    
ans.extend([1] * cnt[1])

for x in ans:
	print(x, end=" ")


N = int(input())
A = [int(a) for a in input().split()]

n1 = A.count(1)
n2 = A.count(2)

if n1*n2==0:
	print(*A)
else:
	s1 = (n1-1)//2*2
	ANS = [2,1]+[1]*s1+[2]*(n2-1)+[1]*(n1-1-s1)
	print(*ANS)


a=int(input())
b=list(map(int,input().split(" ")))
if b.count(1)>=1 and b.count(2)>=1:
	b.remove(1)
	b.remove(2)
	b.sort(reverse=True)
	b.insert(0,2)
	b.insert(1,1)
	print (*b,sep=" ")
else:
	print (*b,sep=" ")


import heapq
import sys
from collections import defaultdict, Counter
from itertools import product


n = int(input())

arr = list(map(int, input().split()))
c = Counter(arr)

if c[1] == 0:
	print('2 ' * n)
elif c[2] == 0:
	print('1 ' * n)
else:
	print('2 1 ' + '2 ' * (c[2] - 1) + '1 ' * (c[1] - 1))


import sys
import copy

line = sys.stdin.readline().strip('\n')
line = sys.stdin.readline().strip('\n')
nums = list(map(int, line.split()))

def primes():
	prim = [1 for i in range(0,400000)]
	prim[1] = 0
	prim[2] = 1
	for i in range(2,400000):
		if(prim[i] == 1):
			tmp = i
			while(tmp+i<400000):
				tmp+=i
				prim[tmp] = 0   
	return prim

ps = primes()
cnt1 = 0
for i in range(len(nums)):
	if(nums[i] == 1):
		cnt1+=1
cnt2 = len(nums)-cnt1
cnt = 0
for i in range(len(nums)):
	if(ps[cnt+1] == 1 and cnt1>0):
		cnt+=1
		cnt1-=1
		print(1, end=' ')
	elif(cnt2>0):
		cnt2-=1
		cnt+=2
		print(2, end=' ')
	else:
		cnt1-=1
		print(1, end=' ')


from collections import Counter


def solve(nums):
	c = Counter(nums)
	if c[2] == 0:
		return ' '.join(map(str, [1 for _ in range(c[1])]))
	elif c[1] == 0:
		return ' '.join(map(str, [2 for _ in range(c[2])]))
	else:
		output = [2, 1]
		c[2] -= 1
		c[1] -= 1
		if c[2] > 0:
			output.extend([2 for _ in range(c[2])])
		if c[1] > 0:
			output.extend([1 for _ in range(c[1])])
		return ' '.join(map(str, output))


def main():
	_ = int(input())
	nums = list(map(int, input().split()))
	print(solve(nums))


def __starting_point():
	main()

__starting_point()


def sol(tiles):
	d = {'1': 0, '2': 0}
	for c in tiles:
		if c == ' ':
			continue
		d[c] += 1
	if d['1'] == 0:
		return ' '.join(['2'] * d['2'])
	if d['2'] == 0:
		return ' '.join(['1'] * d['1'])
	return ' '.join(['2','1'] + ['2']*(d['2']-1) + ['1']*(d['1']-1))

def __starting_point():
	_ = input()
	tiles = input()
	print(sol(tiles))

__starting_point()


# -*- coding: utf-8 -*-
"""
Created on Fri May  3 23:45:36 2019

@author: plosi
"""
di={}

def isPrime(n): 
	if n==1: 
		return False 
	if n<4: 
		return True 
	if n%2==0: 
		return False 
	if n<9: 
		return True 
	if n%3==0: 
		return False 
	else: 
		r=int(n**(1/2)) 
		f=5 
		while f<=r: 
			if n%f==0: 
				return False 
			if n%(f+2)==0: 
				return False 
			f=f+6 
	return True

def mk_arr(num_ones,num_twos): 

	n=0 
	st=""
	while num_ones>0 and num_twos>0: 
		if isPrime(n+1): 
			st=st+"1 " 
			num_ones=num_ones-1
			n=n+1
		else: 
			st=st+"2 "
			num_twos=num_twos-1 
			n=n+2 
	if num_twos==0: 
		for i in range(num_ones): 
			st=st+"1 "
	if num_ones==0: 
		for i in range(num_twos): 
			st=st+"2 "
	
	return st

def main(): 
	n=int(input()) 
	arr=input().split(" ") 
	num_ones=0
	for val in arr: 
		if val=="1": 
			num_ones=num_ones+1 
	st=mk_arr(num_ones,n-num_ones) 
	print(st) 
	
main()  
			
	
	


"""
import bisect
shop=int(input())
price=list(map(int,input().split()))
q=int(input())
price.sort()
for i in range(q):
	m=int(input())
	k=bisect.bisect_right(price,m,0,shop)
	print(len(price)-len(price[k:]))
"""
"""
import math
n,k=map(int,input().split())
lis=[]
for i in range(n):
	p,t=map(int,input().split())
	lis.append([p,t])
lis=sorted(lis,key=lambda x,y:(cmp(x[0],y[0]),cmp(y[1],x[1])),reverse=True)
m=lis[k-1]
print(lis.count(m))
print(lis)
"""
n=int(input())
lis=input().split()
twos=lis.count("2")
ones=n-twos
if(twos==0 or ones==0):
	print(' '.join(lis))
else:
	print("2 1"+" 2"*(twos-1)+" 1"*(ones-1))


import math
read = lambda : map(int, input().split())

def codeforce1149A():
	n = int(input())
	p = list(read())
	if len(p) == 1:
		print(p[0])
		return
	odd, even = 0, 0
	for i in p:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd == 0:
		for i in p:
			print(i, end = ' ')
	elif even == 0:
		for i in p:
			print(i, end = ' ')
	else:
		print(2, 1, end = ' ')
		even -= 1
		odd -= 1
		for _ in range(even):
			print(2, end = " ")
		for _ in range(odd):
			print(1, end = ' ')

def __starting_point():
	codeforce1149A()
__starting_point()


N = int(input())
A = [int(a) for a in input().split()]

n1 = A.count(1)
n2 = A.count(2)

if n1*n2 == 0:
	print(*A)
else:
	print(*([2,1]+[2]*(n2-1)+[1]*(n1-1)))


n=int(input())
a=list(map(int,input().split()))
s=sum(a)
n1=a.count(1)	
n2=n-n1
b=''
if(n2!=0 and n1!=0):
	b='2 1 '
	n2=n2-1
	n1=n1-1
b=b+(n2)*'2 '+(n1)*'1 '
print(b.strip())	


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

input()
a = sorted(map(int, input().split()))[::-1]
a[1:1] = a.pop(),
print(*a)


n=int(input())
l=sorted(list(map(int,input().split())),reverse=True)

ans=l[-1]
l.remove(l[-1])
l.insert(1,ans)
print(*l)



n = int(input())
a = input()
o = a.count('1')
if o == n or o == 0:
	print(a)
else:
	print('2 1 ' + '2 ' * (n - o - 1) + '1 ' * (o - 1))


def make(list):
	a,b=0,0
	for i in range(len(list)):
		if list[i]==1:
			a+=1
		else:
			b+=1
	return a,b
n=int(input())
l=list(map(int,input().strip().split()))
a,b=make(l)
k=[]
if b!=0:
	k.append(2)
	b-=1
if a!=0:
	k.append(1)
	a-=1
while b!=0:
	k.append(2)
	b-=1
while a!=0:
	k.append(1)
	a-=1

print(" ".join(str(x) for x in k))


# -*- coding: utf-8 -*-

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

c1 = (l.count(1))
c2 = (l.count(2))

if c1 == 0 or c2 == 0:
	ll = l
else:
	ll = [2,1]
	l1 = [1]*(c1-1)
	l2 = [2]*(c2-1)
	ll = ll+l2+l1

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