Two semifinals have just been in the running tournament. Each semifinal had n participants. There are n participants advancing to the finals, they are chosen as follows: from each semifinal, we choose k people (0 ≤ 2k ≤ n) who showed the best result in their semifinals and all other places in the finals go to the people who haven't ranked in the top k in their semifinal but got to the n - 2k of the best among the others.

The tournament organizers hasn't yet determined the k value, so the participants want to know who else has any chance to get to the finals and who can go home.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of participants in each semifinal.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 10^9) — the results of the i-th participant (the number of milliseconds he needs to cover the semifinals distance) of the first and second semifinals, correspondingly. All results are distinct. Sequences a_1, a_2, ..., a_{n} and b_1, b_2, ..., b_{n} are sorted in ascending order, i.e. in the order the participants finished in the corresponding semifinal.


-----Output-----

Print two strings consisting of n characters, each equals either "0" or "1". The first line should correspond to the participants of the first semifinal, the second line should correspond to the participants of the second semifinal. The i-th character in the j-th line should equal "1" if the i-th participant of the j-th semifinal has any chances to advance to the finals, otherwise it should equal a "0".


-----Examples-----
Input
4
9840 9920
9860 9980
9930 10020
10040 10090

Output
1110
1100

Input
4
9900 9850
9940 9930
10000 10020
10060 10110

Output
1100
1100



-----Note-----

Consider the first sample. Each semifinal has 4 participants. The results of the first semifinal are 9840, 9860, 9930, 10040. The results of the second semifinal are 9920, 9980, 10020, 10090.  If k = 0, the finalists are determined by the time only, so players 9840, 9860, 9920 and 9930 advance to the finals.  If k = 1, the winners from both semifinals move to the finals (with results 9840 and 9920), and the other places are determined by the time (these places go to the sportsmen who run the distance in 9860 and 9930 milliseconds).  If k = 2, then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Implementation


Solutions:
n = int(input())
a = [None] * n
b = [None] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
for i in range(n):
	if i < n // 2 or a[i] < b[n - i - 1]:
		print(1, end='')
	else:
		print(0, end='')
print()
for i in range(n):
	if i < n // 2 or b[i] < a[n - i - 1]:
		print(1, end='')
	else:
		print(0, end='')


n = int(input())
team1 = [0] * (n + 1)
team2 = [0] * (n + 1)
for i in range(1, n + 1):
	(team1[i], team2[i]) = map(int, input().split())
for i in range(1, n + 1):
	if i <= n // 2 or team1[i] < team2[n - i + 1]:
		print(1, end='')
	else:
		print(0, end='')
print()
for i in range(1, n + 1):
	if i <= n // 2 or team2[i] < team1[n - i + 1]:
		print(1, end='')
	else:
		print(0, end='')


n = int(input())
inp = []
for i in range(n):
	(inp1, inp2) = input().split(' ')
	(inp.append([int(inp1), 1]), inp.append([int(inp2), 2]))
(result1, result2, result3) = ('', '', '')
j = 0
inp.sort()
inpSort = inp
for i in inpSort:
	if j == n:
		break
	if i[1] == 1:
		result1 += '1'
	else:
		result2 += '1'
	j += 1
for i in range(n // 2):
	result3 += '1'
if len(result1) > len(result3):
	for i in range(n - len(result1)):
		result1 += '0'
	for i in range(n - len(result3)):
		result3 += '0'
	result = result1 + '\n' + result3
elif len(result2) > len(result3):
	for i in range(n - len(result2)):
		result2 += '0'
	for i in range(n - len(result3)):
		result3 += '0'
	result = result3 + '\n' + result2
else:
	for i in range(n - len(result3)):
		result3 += '0'
	result = result3 + '\n' + result3
print(result)


n = int(input())
p1 = ['0' for _ in range(n)]
p2 = ['0' for _ in range(n)]
t1 = []
t2 = []
for i in range(n):
	(a, b) = map(int, input().split())
	t1.append((a, i))
	t2.append((b, i))
t2.sort()
t1.sort()
for k in range(n // 2):
	p1[t1[k][1]] = '1'
	p2[t2[k][1]] = '1'
i = 0
j = 0
for k in range(n):
	if t1[i][0] < t2[j][0]:
		p1[t1[i][1]] = '1'
		i += 1
	else:
		p2[t2[j][1]] = '1'
		j += 1
print(''.join(p1))
print(''.join(p2))


n = int(input())
a = [[0, 0]] * n
b = [[0, 0]] * n
for i in range(n):
	(x, y) = input().split()
	a[i] = [int(x), 0]
	b[i] = [int(y), 0]
j = 0
k = 0
for i in range(n):
	if a[j][0] < b[k][0]:
		a[j][1] = 1
		j += 1
	else:
		b[k][1] = 1
		k += 1
k = n // 2
for i in range(k):
	a[i][1] = 1
	b[i][1] = 1
s1 = ''
s2 = ''
for i in range(n):
	s1 += str(a[i][1])
	s2 += str(b[i][1])
print(s1)
print(s2)


n = int(input())
a = []
b = []
for i in range(n):
	pair = input().split()
	a.append(int(pair[0]))
	b.append(int(pair[1]))
flag = 0
for i in range(n):
	if i < n // 2:
		print('1', end='')
	else:
		if flag == 0 and a[i] >= b[n - i - 1]:
			flag = 1
		if flag == 0:
			print('1', end='')
		else:
			print('0', end='')
print()
flag = 0
for i in range(n):
	if i < n // 2:
		print('1', end='')
	else:
		if flag == 0 and b[i] >= a[n - i - 1]:
			flag = 1
		if flag == 0:
			print('1', end='')
		else:
			print('0', end='')


n = int(input())
(a, b) = ([], [])
for _ in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
res_a = ['0'] * n
res_b = ['0'] * n
for i in range(n // 2):
	res_a[i] = res_b[i] = '1'
i1 = i2 = 0
i = 0
while i < n:
	if a[i1] < b[i2]:
		res_a[i1] = '1'
		i1 += 1
	else:
		res_b[i2] = '1'
		i2 += 1
	i += 1
print(''.join(res_a) + '\n' + ''.join(res_b))


def chose_p(arr, brr, k):
	n = len(arr)
	crr = []
	for i in range(k):
		crr.append(arr[i])
		arr[i] = 0
	for i in range(k):
		crr.append(brr[i])
		brr[i] = 0
	drr = [x for x in arr if x] + [x for x in brr if x]
	drr.sort()
	for i in range(n - 2 * k):
		crr.append(drr[i])
	return crr
n = int(input())
arr = []
brr = []
for _ in range(n):
	(x, y) = map(int, input().split())
	arr.append(x)
	brr.append(y)
s = set()
crr = chose_p(arr[:], brr[:], 0)
drr = chose_p(arr[:], brr[:], n // 2)
s.update(crr, drr)
for (i, x) in enumerate(arr):
	arr[i] = str(int(x in s))
for (i, x) in enumerate(brr):
	brr[i] = str(int(x in s))
print(''.join(arr))
print(''.join(brr))


from sys import stdin, setrecursionlimit
n = int(stdin.readline().strip())
first = []
second = []
for _ in range(n):
	(f, s) = list(map(int, stdin.readline().split()))
	first.append(f)
	second.append(s)
string1 = ['0'] * n
string2 = ['0'] * n
i = 0
j = 0
count = 0
while i < n and j < n and (count < n):
	if first[i] < second[j]:
		count += 1
		string1[i] = '1'
		i += 1
	else:
		count += 1
		string2[j] = '1'
		j += 1
for i in range(n // 2):
	string1[i] = '1'
	string2[i] = '1'
print(''.join(string1))
print(''.join(string2))


a = int(input())
z = [[1] * (a // 2) + [0] * (a - a // 2), [1] * (a // 2) + [0] * (a - a // 2)]
k = []
for i in range(a):
	(u, v) = map(int, input().split())
	k += [[u, 0, i], [v, 1, i]]
k.sort()
for i in k[:a]:
	z[i[1]][i[2]] = 1
for i in z:
	print(''.join(map(str, i)))


n = int(input())
a = []
for i in range(2):
	a.append([0] * n)
k = n // 2
s1 = []
s2 = []
for i in range(n):
	(x, y) = map(int, input().split())
	s1.append(x)
	s2.append(y)
for i in range(k):
	a[0][i] = 1
	a[1][i] = 1
left = n - 2 * k
if left == 1:
	if s1[k] < s2[k]:
		a[0][k] = 1
	else:
		a[1][k] = 1
i = 0
j = 0
cnt = 0
while cnt < n:
	if i < n and s1[i] < s2[j]:
		a[0][i] = 1
		i += 1
	else:
		a[1][j] = 1
		j += 1
	cnt += 1
for i in range(len(a)):
	for j in range(len(a[i])):
		print(a[i][j], end='')
	print()


n = int(input())
a = list((tuple(map(int, input().split())) for i in range(n)))
m = n // 2
c = list(('1' for i in range(m)))
d = list(('1' for i in range(m)))
for i in range(m, n):
	if a[i][0] < a[n - i - 1][1]:
		c.append('1')
	else:
		c.append('0')
	if a[n - i - 1][0] > a[i][1]:
		d.append('1')
	else:
		d.append('0')
print(''.join(c))
print(''.join(d))


from sys import stdin, stdout
a = int(stdin.readline())
z = [[1] * (a // 2) + [0] * (a - a // 2) + ['\n'], [1] * (a // 2) + [0] * (a - a // 2)]
k = []
for i in range(a):
	(u, v) = map(int, stdin.readline().split())
	k += [[u, 0, i], [v, 1, i]]
k.sort()
for i in k[:a]:
	z[i[1]][i[2]] = 1
for i in z:
	stdout.write(''.join(map(str, i)))


n = int(input())
(a, b) = zip(*(map(int, input().split()) for _ in range(n)))
i = j = 0
while i < n and j < n and (i + j < n):
	if a[i] < b[j]:
		i += 1
	else:
		j += 1

def p(x):
	return ('1' * max(n // 2, x)).ljust(n, '0')
print(p(i))
print(p(j))


def semifinals(l1, l2):
	output1 = [0] * len(l1)
	output2 = [0] * len(l2)
	n = len(l1)
	k = len(l1) // 2
	output1[0:k] = [1] * k
	output2[0:k] = [1] * k
	i = k
	while i < len(l1):
		if l1[i] < l2[n - i - 1]:
			output1[i] = 1
		if l2[i] < l1[n - i - 1]:
			output2[i] = 1
		i += 1
	output1 = ''.join([str(x) for x in output1])
	output2 = ''.join([str(x) for x in output2])
	return (output1, output2)
n = int(input())
l1 = []
l2 = []
for i in range(n):
	a = [int(x) for x in input().split()]
	l1.append(a[0])
	l2.append(a[1])
print(semifinals(l1, l2)[0])
print(semifinals(l1, l2)[1])


n = int(input())
semi1 = [0] * (n + 1)
semi2 = [0] * (n + 1)
for i in range(1, n + 1):
	(semi1[i], semi2[i]) = map(int, input().split())
semi1Selected = [0] * (n + 1)
semi2Selected = [0] * (n + 1)
for i in range(1, n + 1):
	if i <= n // 2:
		semi1Selected[i] = 1
		semi2Selected[i] = 1
	else:
		if semi1[i] < semi2[n - i + 1]:
			semi1Selected[i] = 1
		if semi2[i] < semi1[n - i + 1]:
			semi2Selected[i] = 1
for i in range(1, n + 1):
	print(semi1Selected[i], end='')
print()
for i in range(1, n + 1):
	print(semi2Selected[i], end='')


num_par = int(input())
semi1 = []
semi2 = []
semi1_result = ''
semi2_result = ''
k = num_par // 2
for i in range(num_par):
	a = input()
	a = a.split()
	semi1.append(int(a[0]))
	semi2.append(int(a[1]))
a = 0
b = 0
for i in range(num_par):
	if semi1[a] < semi2[b]:
		a += 1
	else:
		b += 1
for i in range(num_par):
	if i < a or i < k:
		semi1_result += '1'
	else:
		semi1_result += '0'
	if i < b or i < k:
		semi2_result += '1'
	else:
		semi2_result += '0'
print(semi1_result)
print(semi2_result)


import sys

def read(line):
	return [int(c) for c in line.strip().split()]

def main():
	test = sys.stdin.readlines()
	n = int(test[0])
	first_game = {}
	second_game = {}
	aa = []
	bb = []
	pos = 1
	for i in range(1, n + 1):
		(a, b) = read(test[i])
		first_game[a] = pos
		second_game[b] = pos
		aa.append(a)
		bb.append(b)
		pos += 1
	i = j = 0
	total = {}
	pos = 1
	while i < n and j < n:
		if aa[i] < bb[j]:
			total[aa[i]] = pos
			i += 1
		else:
			total[bb[j]] = pos
			j += 1
		pos += 1
	for k in range(i, n):
		total[aa[k]] = pos
		pos += 1
	for k in range(j, n):
		total[bb[k]] = pos
		pos += 1
	out1 = []
	for p in first_game:
		out1.append(1 if first_game[p] <= n // 2 or total[p] <= n else 0)
	out2 = []
	for p in second_game:
		out2.append(1 if second_game[p] <= n // 2 or total[p] <= n else 0)
	print(*out1, sep='')
	print(*out2, sep='')
main()


n = int(input())
(a, b) = ([], [])
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
ans = ''
for i in range(n):
	if i < n // 2 or a[i] < b[n - 1 - i]:
		ans += '1'
	else:
		ans += '0'
ans += '\n'
for i in range(n):
	if i < n // 2 or b[i] < a[n - 1 - i]:
		ans += '1'
	else:
		ans += '0'
print(ans)


import math
import sys
import collections
from collections import Counter
import bisect
import string

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

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

def get_string():
	return sys.stdin.readline().strip()
for tc in range(1):
	n = int(input())
	arr = []
	a1 = []
	b1 = []
	for i in range(n):
		(a, b) = get_ints()
		a1.append(a)
		b1.append(b)
		arr.append(a)
		arr.append(b)
	arr.sort()
	maxim = arr[n - 1]
	ans1 = ''
	ans2 = ''
	for i in range(n):
		if i < n // 2:
			ans1 += '1'
			ans2 += '1'
			continue
		if a1[i] <= maxim:
			ans1 += '1'
		else:
			ans1 += '0'
		if b1[i] <= maxim:
			ans2 += '1'
		else:
			ans2 += '0'
	print(ans1)
	print(ans2)


n = int(input())
(a, b) = ([0] * n, [0] * n)
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
k = n // 2
i = j = k - 1
if 2 * k < n:
	if a[k] < b[k]:
		(i, j) = (k, k - 1)
	else:
		(i, j) = (k - 1, k)
(x, y) = (i + 1, j)
while x < n and y >= 0 and (a[x] < b[y]):
	x += 1
	y -= 1
(u, v) = (i, j + 1)
while u >= 0 and v < n and (a[u] > b[v]):
	u -= 1
	v += 1
(i, j) = (max(i, x), max(j, v))
print('1' * i + '0' * (n - i))
print('1' * j + '0' * (n - j))


n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
x = [0] * n
y = [0] * n
i = 0
j = 0
cnt = 0
while i < n or j < n:
	if a[i] <= b[j]:
		x[i] = 1
		i += 1
	else:
		y[j] = 1
		j += 1
	cnt += 1
	if cnt == n:
		break
for i in range(int(n / 2)):
	x[i] = 1
	y[i] = 1
print(''.join((str(u) for u in x)))
print(''.join((str(v) for v in y)))


n = int(input())
semi1 = [0] * n
semi2 = [0] * n
count = a = b = k = 0
final1 = [0] * n
final2 = [0] * n
for i in range(n):
	(semi1[i], semi2[i]) = map(int, input().rstrip().split())
final1[:n // 2] = final2[:n // 2] = [1] * (n // 2)
while (a < n) & (b < n):
	if semi1[a] <= semi2[b]:
		if final1[a] == 0:
			final1[a] = 1
		count += 1
		a += 1
	else:
		if final2[b] == 0:
			final2[b] = 1
		b += 1
		count += 1
	if count == n:
		break
print(''.join(list(map(str, final1))))
print(''.join(list(map(str, final2))))


def calc_chances_matrix(_n, _a, _b):
	k = n // 2
	chances_matrix = [[1] * k + [0] * (n - k) for j in range(2)]
	last_a = k - 1
	last_b = k - 1
	if n % 2 == 1:
		if _a[k] < _b[k]:
			last_a += 1
			chances_matrix[0][k] = 1
		else:
			last_b += 1
			chances_matrix[1][k] = 1
	while last_a < n - 1 and last_b < n - 1:
		if _a[last_a + 1] < _b[n - (last_a + 1) - 1]:
			last_a += 1
			chances_matrix[0][last_a] = 1
		elif _b[last_b + 1] < _a[n - (last_b + 1) - 1]:
			last_b += 1
			chances_matrix[1][last_b] = 1
		else:
			break
	return chances_matrix
n = int(input())
(a, b) = ([], [])
for i in range(n):
	(ai, bi) = map(int, input().split())
	a.append(ai)
	b.append(bi)
print(*calc_chances_matrix(n, a, b)[0], sep='')
print(*calc_chances_matrix(n, a, b)[1], sep='')


n = int(input())
a = []
b = []
c = []
l = [[1] * (n // 2) + [0] * (n - n // 2) for _ in range(2)]
for i in range(n):
	(x, y) = map(int, input().strip().split())
	a.append(x)
	b.append(y)
	c += [(x, i, 0), (y, i, 1)]
c.sort()
for (i, xs) in enumerate(c):
	(x, y, z) = xs
	if y >= n // 2 and i < n:
		l[z][y] = 1
for xs in l:
	print(''.join(map(str, xs)))


import sys
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
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 sys.stdin.readline().strip()

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

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)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(ele, end='\n')
n = L()[0]
A = []
B = []
for i in range(n):
	(a, b) = L()
	A.append(a)
	B.append(b)
Z = sorted(A + B)[n - 1]
for i in range(n):
	if i < n // 2 or A[i] <= Z:
		print(1, end='')
	else:
		print(0, end='')
print()
for i in range(n):
	if i < n // 2 or B[i] <= Z:
		print(1, end='')
	else:
		print(0, end='')
print()
endtime = time.time()


n = int(input())
(a, b) = ([], [])
for _ in range(n):
	(x, y) = map(int, input().split())
	a += [x]
	b += [y]
i = j = 0
while i < n and j < n and (i + j < n):
	if a[i] < b[j]:
		i += 1
	else:
		j += 1
print(('1' * max(n // 2, i)).ljust(n, '0'))
print(('1' * max(n // 2, j)).ljust(n, '0'))


class Participant:

	def __init__(self, value, i, j):
		self.value = value
		self.i = i
		self.j = j

def merge(ans, participants1, participants2, n):
	i = 0
	j = 0
	k = 0
	while i < n and j < n and (k < n):
		if participants1[i].value < participants2[j].value:
			ans[participants1[i].i][participants1[i].j] = '1'
			i += 1
		else:
			ans[participants2[j].i][participants2[j].j] = '1'
			j += 1
		k += 1
n = int(input())
participants1 = []
participants2 = []
ans = []
k = n // 2
win1 = ''
win2 = ''
for i in range(n):
	(first, second) = map(int, input().split())
	participant1 = Participant(first, i, 0)
	participant2 = Participant(second, i, 1)
	participants1.append(participant1)
	participants2.append(participant2)
	if i < k:
		ans.append(['1', '1'])
		win1 += '1'
		win2 += '1'
	else:
		ans.append(['0', '0'])
merge(ans, participants1, participants2, n)
for i in range(k, n):
	win1 += ans[i][0]
	win2 += ans[i][1]
print(win1)
print(win2)


from math import gcd
import sys

def inp():
	return sys.stdin.readline().strip()
t = 1
for _ in range(t):
	n = int(inp())
	time = []
	timea = []
	timeb = []
	for i in range(n):
		(a, b) = map(int, inp().split())
		timea.append(a)
		timeb.append(b)
	chance1 = ['0'] * n
	chance2 = ['0'] * n
	ia = 0
	ib = 0
	for i in range(n):
		if timea[ia] < timeb[ib]:
			chance1[ia] = '1'
			ia = ia + 1
		else:
			chance2[ib] = '1'
			ib = ib + 1
	for i in range(n // 2):
		chance1[i] = '1'
		chance2[i] = '1'
	print(''.join(chance1))
	print(''.join(chance2))


n = int(input())
arrLeft = []
arrRight = []
for i in range(n):
	(l, r) = map(int, input().split())
	arrLeft.append(l)
	arrRight.append(r)
k = n // 2
arrResultLeft = [0] * n
arrResultRight = [0] * n
t = 0
for j in range(0, k):
	arrResultLeft[j] = 1
	arrResultRight[j] = 1
x = 0
y = 0
while x < n and y < n and (t < n):
	if arrLeft[x] < arrRight[y]:
		arrResultLeft[x] = 1
		x += 1
	elif arrRight[y] < arrLeft[x]:
		arrResultRight[y] = 1
		y += 1
	t += 1
for i in range(n):
	print(arrResultLeft[i], end='')
print()
for i in range(n):
	print(arrResultRight[i], end='')


def readInputs():
	global n, la, lb
	n = int(input())
	la = n * [(0, 0)]
	lb = n * [(0, 0)]
	for i in range(n):
		(a, b) = map(int, input().split())
		la[i] = (1, i, a)
		lb[i] = (2, i, b)

def solve():
	lc = la + lb
	lc.sort(key=lambda x: x[2], reverse=False)
	laOk = n * ['0']
	lbOk = n * ['0']
	nb1 = 0
	nb2 = 0
	for i in range(len(lc)):
		if lc[i][0] == 1:
			nb1 += 1
			if nb1 <= n // 2 or nb1 + nb2 <= n:
				laOk[lc[i][1]] = '1'
		else:
			nb2 += 1
			if nb2 <= n // 2 or nb1 + nb2 <= n:
				lbOk[lc[i][1]] = '1'
	print(''.join(laOk))
	print(''.join(lbOk))

def main():
	readInputs()
	solve()
main()


import math
import heapq

def main():
	n = eval(input())
	semi1 = []
	semi2 = []
	has_chances = [[], []]
	for u in range(n):
		f = input().split()
		semi1.append((int(f[0]), 0, u))
		semi2.append((int(f[1]), 1, u))
		has_chances[0].append('0')
		has_chances[1].append('0')
	all_of_them = list(heapq.merge(semi1, semi2))
	k = 0
	for i in range(n - 2 * k):
		has_chances[all_of_them[i][1]][all_of_them[i][2]] = '1'
	k = n // 2
	for i in range(k):
		has_chances[0][i] = '1'
		has_chances[1][i] = '1'
	print(''.join(has_chances[0]))
	print(''.join(has_chances[1]))
main()


n = int(input())
sem1 = []
sem2 = []
l = [0, 0]
for cont in range(0, n):
	l = list(map(int, input().split()))
	sem1.append(l[0])
	sem2.append(l[1])
kmax = int(n / 2)
max1 = 0
max2 = 0
for cont in range(0, n):
	if sem1[max1] < sem2[max2]:
		max1 += 1
	else:
		max2 += 1
ris1 = ['1'] * max([max1, kmax])
ris2 = ['1'] * max([max2, kmax])
ris1 = ris1 + ['0'] * (n - len(ris1))
ris2 = ris2 + ['0'] * (n - len(ris2))
print(''.join(ris1))
print(''.join(ris2))


Narray = int(input())
Aarray = []
Barray = []
k = int(Narray / 2)
(a, b, p, q) = (0, 0, 0, 0)
for i in range(Narray):
	Carray = input().split()
	if q + p <= Narray:
		Aarray.append(int(Carray[0]))
		Barray.append(int(Carray[1]))
		if Aarray[0] < Barray[0]:
			Aarray.pop(0)
			p += 1
			q += 0
		else:
			Barray.pop(0)
			p += 0
			q += 1
		if q + p == Narray:
			(a, b) = (p, q)
	else:
		continue
if a < b:
	print('1' * k + '0' * (Narray - k))
	print('1' * (Narray - a) + '0' * a)
elif a == b:
	print('1' * k + '0' * (Narray - k))
	print('1' * k + '0' * (Narray - k))
else:
	print('1' * (Narray - b) + '0' * b)
	print('1' * k + '0' * (Narray - k))


def main():
	n = int(input())
	s1 = []
	s2 = []
	for i in range(n):
		temp = input().split(' ')
		s1.append(int(temp[0]))
		s2.append(int(temp[1]))
	r1 = ['0' for i in range(n)]
	r2 = ['0' for i in range(n)]
	i = 0
	j = 0
	for k in range(n):
		if s1[i] < s2[j]:
			r1[i] = '1'
			i += 1
		else:
			r2[j] = '1'
			j += 1
	for k in range(n // 2):
		r1[k] = '1'
		r2[k] = '1'
	r1 = ''.join(r1)
	r2 = ''.join(r2)
	print(r1)
	print(r2)
main()


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))

def solve():
	n = int(input())
	results = []
	for i in range(n):
		(a, b) = read_tuple(int)
		results.append((0, i, a))
		results.append((1, i, b))
	results.sort(key=lambda x: x[2])
	passed1 = [0 for _ in range(n)]
	passed2 = [0 for _ in range(n)]
	for (hf, i, _) in results[:n]:
		if hf == 0:
			passed1[i] = 1
		elif hf == 1:
			passed2[i] = 1
	(hf1, hf2) = (n // 2, n // 2)
	for (hf, i, _) in results:
		if hf1 and hf == 0:
			passed1[i] = 1
			hf1 -= 1
		elif hf2 and hf == 1:
			passed2[i] = 1
			hf2 -= 1
	print(''.join(map(str, passed1)))
	print(''.join(map(str, passed2)))
solve()


n = int(input())
a = []
b = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
x = [0] * n
y = [0] * n
i = 0
j = 0
cnt = 0
while i < n and j < n:
	if a[i] > b[j]:
		y[j] = 1
		j += 1
		cnt += 1
	elif a[i] <= b[j]:
		x[i] = 1
		i += 1
		cnt += 1
	if cnt == n:
		break
for i in range(n // 2):
	x[i] = 1
for j in range(n // 2):
	y[j] = 1
for i in range(n):
	print(x[i], end='')
print()
for j in range(n):
	print(y[j], end='')


n = int(input())
(A, B, C, D) = ([], [], [], [])
for i in range(n):
	(tempC, tempD) = map(int, input().split())
	C.append(tempC)
	D.append(tempD)
for i in range(n // 2):
	A.append('1')
	B.append('1')
for i in range(n // 2, n, 1):
	A.append('0')
	B.append('0')
(a, b) = (0, 0)
for i in range(n):
	if C[a] < D[b]:
		A[a] = '1'
		a += 1
	else:
		B[b] = '1'
		b += 1
print(''.join(A))
print(''.join(B))


n = int(input())
(a, b) = ([], [])
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
p = q = 0
c = 0
while c < n:
	if a[p] < b[q]:
		p += 1
	else:
		q += 1
	c += 1
p0 = max(p, n // 2)
print('1' * p0 + '0' * (n - p0))
q0 = max(q, n // 2)
print('1' * q0 + '0' * (n - q0))


n = int(input())
a = []
b = []
for i in range(n):
	(ai, bi) = map(int, input().split())
	a.append(ai)
	b.append(bi)
first = [0] * n
second = [0] * n
for ri in range(n // 2):
	first[ri] = 1
	second[ri] = 1
i = n
ia = 0
ib = 0
while i > 0:
	if a[ia] < b[ib]:
		first[ia] = 1
		ia += 1
	else:
		second[ib] = 1
		ib += 1
	i -= 1
print(''.join((str(fi) for fi in first)))
print(''.join((str(si) for si in second)))


import collections
import functools
import math
import sys
import bisect

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

def semifinal():
	n = int(input())
	l = [list(In()) for _ in range(n)]
	fir = ['0'] * n
	sec = ['0'] * n
	(pos, lpos) = (0, 0)
	k = n
	while pos < n and lpos < n and k:
		if l[pos][0] > l[lpos][1]:
			sec[lpos] = '1'
			lpos += 1
		else:
			fir[pos] = '1'
			pos += 1
		k -= 1
	while k:
		while pos < n and k:
			fir[pos] = '1'
			pos += 1
			k -= 1
		while lpos < n and k:
			sec[lpos] = '1'
			lpos += 1
			k -= 1
	for i in range(n // 2):
		fir[i] = sec[i] = '1'
	print(*fir, sep='')
	print(*sec, sep='')
semifinal()


n = int(input())
Team1 = (n + 7) * [0]
Team2 = (n + 7) * [0]
for i in range(1, n + 1):
	(Team1[i], Team2[i]) = map(int, input().split())
for i in range(1, n + 1):
	if i <= n // 2 or Team1[i] < Team2[n - i + 1]:
		print(1, end='')
	else:
		print(0, end='')
print()
for i in range(1, n + 1):
	if i <= n // 2 or Team2[i] < Team1[n - i + 1]:
		print(1, end='')
	else:
		print(0, end='')


n = int(input())
a = []
b = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
i = j = 0
ans1 = ['0'] * n
ans2 = ['0'] * n
for k in range(n):
	if a[i] < b[j]:
		ans1[i] = '1'
		i += 1
	else:
		ans2[j] = '1'
		j += 1
for i in range(n // 2):
	ans1[i] = ans2[i] = '1'
for i in range(n):
	print(ans1[i], end='')
print()
for i in range(n):
	print(ans2[i], end='')
print()


from sys import stdin
n = int(stdin.readline())
a = tuple((tuple(map(int, ln.split())) for ln in stdin))
m = n // 2
a1 = list(('1' for i in range(m)))
a2 = list(('1' for i in range(m)))
for i in range(m, n):
	if a[i][0] < a[n - i - 1][1]:
		a1.append('1')
	else:
		a1.append('0')
	if a[n - i - 1][0] > a[i][1]:
		a2.append('1')
	else:
		a2.append('0')
print(''.join(a1))
print(''.join(a2))


n = int(input())
(A, B) = ([], [])
p = q = 0
k = n // 2
for i in range(n):
	(a, b) = map(int, input().split())
	A.append(a)
	B.append(b)
for i in range(n):
	if A[p] < B[q]:
		p += 1
	else:
		q += 1
for i in range(n):
	print(1 if i < p or i < k else 0, end='')
print()
for i in range(n):
	print(1 if i < q or i < k else 0, end='')
print()


n = int(input())
(semi1, semi2, both) = ([], [], [])
(ans1, ans2) = ('', '')
for i in range(n):
	(a, b) = map(int, input().split())
	semi1.append(a)
	semi2.append(b)
	both.append((a, 1))
	both.append((b, 2))
both = sorted(both, key=lambda k: k[0])
for i in range(n // 2):
	ans1 += '1'
	ans2 += '1'
(cnt1, cnt2) = (0, 0)
for i in range(n):
	if both[i][1] == 1:
		cnt1 += 1
		if len(ans1) < cnt1:
			ans1 += '1'
	else:
		cnt2 += 1
		if len(ans2) < cnt2:
			ans2 += '1'
while len(ans1) < n:
	ans1 += '0'
while len(ans2) < n:
	ans2 += '0'
print(ans1, ans2, sep='\n')


import sys
from math import *

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
n = mint()
a = [0] * n
b = [0] * n
c = [0] * n
d = [0] * n
for i in range(n):
	(a[i], b[i]) = mints()
for i in range(n // 2):
	c[i] = 1
	d[i] = 1
x = 0
y = 0
while x + y < n:
	if x < n and y < n:
		if a[x] < b[y]:
			x += 1
		else:
			y += 1
	elif x < n:
		x += 1
	else:
		y += 1
for i in range(x):
	c[i] = 1
for i in range(y):
	d[i] = 1
print(*c, sep='')
print(*d, sep='')


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 = []
b = []
for _ in range(n):
	(x, y) = value()
	a.append(x)
	b.append(y)
chanceA = [0] * n
chanceB = [0] * n
ia = 0
ib = 0
for i in range(n):
	if a[ia] < b[ib]:
		chanceA[ia] = 1
		ia += 1
	else:
		chanceB[ib] = 1
		ib += 1
for i in range(n // 2):
	chanceA[i] = 1
	chanceB[i] = 1
print(*chanceA, sep='')
print(*chanceB, sep='')


n = int(input())
a = []
b = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
k = 0
checka = [0] * (n + 1)
checkb = [0] * (n + 1)
count = 0
i = 0
j = 0
while count < n - 2 * k:
	if a[i] < b[j]:
		checka[i] = 1
		i += 1
	else:
		checkb[j] = 1
		j += 1
	count += 1
while 2 * k <= n:
	if k - 1 >= 0:
		checka[k - 1] = 1
		checkb[k - 1] = 1
	k += 1
for i in range(n):
	print(checka[i], end='')
print()
for i in range(n):
	print(checkb[i], end='')


n = int(input())
(semi_1, semi_2) = ([], [])
for _ in range(n):
	(a, b) = map(int, input().split())
	semi_1.append(a)
	semi_2.append(b)
(marked_1, marked_2) = ([False] * n, [False] * n)
i = j = 0
for count in range(n):
	if semi_1[i] < semi_2[j]:
		marked_1[i] = True
		i += 1
	else:
		marked_2[j] = True
		j += 1
for i in range(n):
	print(1 if i < n // 2 or marked_1[i] else 0, end='')
print()
for i in range(n):
	print(1 if i < n // 2 or marked_2[i] else 0, end='')


n = int(input())
groupA = [0] * n
groupB = [0] * n
for i in range(n):
	(groupA[i], groupB[i]) = map(int, input().split())
groupAChoices = [0] * n
groupBChoices = [0] * n
k = n // 2
for i in range(k):
	groupAChoices[i] = 1
	groupBChoices[i] = 1
for i in range(k, n):
	if groupA[i] < groupB[n - i - 1]:
		groupAChoices[i] = 1
	if groupB[i] < groupA[n - i - 1]:
		groupBChoices[i] = 1
for i in range(n):
	print(groupAChoices[i], end='')
print()
for i in range(n):
	print(groupBChoices[i], end='')


import sys
import string
import math
from collections import defaultdict
from functools import lru_cache
from collections import Counter
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

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

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def main():
	n = iline()
	l = []
	r = []
	for i in range(n):
		(x, y) = mi(line())
		l.append((x, i, 'l'))
		r.append((y, i, 'r'))
	tot = l + r
	l.sort()
	r.sort()
	tot.sort()
	pos_l = [0 for _ in range(len(l))]
	pos_r = [0 for _ in range(len(l))]
	for i in range(len(l) // 2):
		(_, il, _) = l[i]
		pos_l[il] = 1
		(_, ir, _) = r[i]
		pos_r[ir] = 1
	for i in range(len(l)):
		(_, ii, a) = tot[i]
		if a == 'l':
			pos_l[ii] = 1
		else:
			pos_r[ii] = 1
	print(jsns(pos_l))
	print(jsns(pos_r))
main()


n = int(input())
semi1 = []
semi2 = []
k = int(n / 2)
ans1 = [0 for i in range(n)]
ans2 = [0 for i in range(n)]
for i in range(n):
	(temp1, temp2) = map(int, input().split())
	semi1.append(temp1)
	semi2.append(temp2)
count = 0
ls = [0, k]
for l in ls:
	count = n - 2 * l
	i = 0
	j = 0
	for x in range(l):
		ans1[x] = 1
		ans2[x] = 1
	while i + j <= count - 1:
		if semi1[i + l] < semi2[j + l]:
			ans1[i + l] = 1
			i += 1
		elif semi1[i + l] > semi2[j + l]:
			ans2[j + l] = 1
			j += 1
print(''.join(map(str, ans1)))
print(''.join(map(str, ans2)))


from sys import stdin, stdout
from os import path
rd = lambda : stdin.readline().strip()
wr = stdout.write
if path.exists('input.txt'):
	stdin = open('input.txt', 'r')
import time
x = int(rd())
(a, b) = ([], [])
for _ in range(x):
	(a1, b1) = map(int, rd().split())
	a.append(a1)
	b.append(b1)
i = j = 0
while i + j < x:
	if a[i] < b[j]:
		i += 1
	else:
		j += 1
i = max(x // 2, i)
j = max(x // 2, j)
print('1' * i + '0' * (x - i))
print('1' * j + '0' * (x - j))


n = int(input())
l1 = [0] * n
l2 = [0] * n
ls1 = ['0'] * n
ls2 = ['0'] * n
for i in range(n):
	(a, b) = map(int, input().split())
	l1[i] = a
	l2[i] = b
tl = [0, n // 2]
for k in tl:
	for h in range(k):
		ls1[h] = '1'
		ls2[h] = '1'
	x = n - 2 * k
	i = k
	j = k
	while x > 0:
		if l1[i] < l2[j]:
			ls1[i] = '1'
			i = i + 1
		else:
			ls2[j] = '1'
			j = j + 1
		x = x - 1
ls1 = ''.join(ls1)
ls2 = ''.join(ls2)
print(ls1)
print(ls2)


a = int(input())
pol1 = []
pol2 = []
for i in range(a):
	(x, y) = map(int, input().split())
	pol1.append(x)
	pol2.append(y)
f = 0
s = 0
ans1 = [0] * a
ans2 = [0] * a
count = 0
while True:
	count += 1
	if pol1[f] < pol2[s]:
		ans1[f] = 1
		f += 1
	else:
		ans2[s] = 1
		s += 1
	if count == a:
		break
for i in range(a // 2):
	ans1[i] = 1
	ans2[i] = 1
s = ''
for i in ans1:
	s += str(i)
print(s)
s = ''
for i in ans2:
	s += str(i)
print(s)


n = int(input())
arr = [0] * n
for i in range(n):
	arr[i] = list(map(int, input().split()))
k = n // 2
left = [0] * n
right = [0] * n
for i in range(k):
	left[i] = 1
	right[i] = 1
a = 0
b = 0
for i in range(n):
	if arr[a][0] < arr[b][1]:
		left[a] = 1
		a += 1
	else:
		right[b] = 1
		b += 1
print(''.join(map(str, left)))
print(''.join(map(str, right)))


n = int(input())
a = []
b = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
final_1 = [False] * n
final_2 = [False] * n
i = j = 0
chosen = 0
while chosen < n:
	if a[i] < b[j]:
		final_1[i] = True
		i += 1
		chosen += 1
	else:
		final_2[j] = True
		j += 1
		chosen += 1
for i in range(n):
	if final_1[i] or i < n // 2:
		print(1, end='')
	else:
		print(0, end='')
print()
for i in range(n):
	if final_2[i] or i < n // 2:
		print(1, end='')
	else:
		print(0, end='')


n = int(input())
k = []
a = []
b = []
for i in range(n):
	(A, B) = map(int, input().split())
	a.append(A)
	b.append(B)
la = 0
lb = 0
aind = [0] * n
bind = [0] * n
for i in range(n):
	if a[la] < b[lb]:
		aind[la] = 1
		la += 1
	else:
		bind[lb] = 1
		lb += 1
for i in range(n // 2):
	aind[i] = 1
	bind[i] = 1
for i in aind:
	print(i, end='')
print('')
for i in bind:
	print(i, end='')


s1 = []
s2 = []
n = int(input())
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	s1.append(a)
	s2.append(b)
k = n // 2
ans1 = ['0'] * n
ans2 = ['0'] * n
j = 0
i = 0
while i + j < n:
	if s1[i] < s2[j]:
		ans1[i] = '1'
		i += 1
	else:
		ans2[j] = '1'
		j += 1
i = 0
while i < k:
	ans1[i] = '1'
	ans2[i] = '1'
	i += 1
ans1 = ''.join(ans1)
ans2 = ''.join(ans2)
print(ans1)
print(ans2)


n = int(input())
k = int(n / 2)
s1 = '1' * int(n / 2) + '0' * (n - int(n / 2))
s2 = '1' * int(n / 2) + '0' * (n - int(n / 2))
s1 = list(s1)
s2 = list(s2)
a = []
b = []
for i in range(n):
	(c, d) = input().split()
	a.append(int(c))
	b.append(int(d))
for i in range(k, n):
	if a[i] < b[n - i - 1]:
		s1[i] = '1'
	if b[i] < a[n - i - 1]:
		s2[i] = '1'
print(''.join(s1))
print(''.join(s2))


n = int(input())
first = []
second = []
index_a = 0
index_b = 0
for i in range(n):
	pair = list(map(int, input().split()))
	first.append(pair[0])
	second.append(pair[1])
	if first[index_a] < second[index_b]:
		index_a += 1
	elif first[index_a] > second[index_b]:
		index_b += 1
if index_a < n / 2:
	index_a = n // 2
elif index_b < n / 2:
	index_b = n // 2
for i in range(index_a):
	print('1', end='')
for i in range(index_a, n):
	print('0', end='')
print()
for i in range(index_b):
	print('1', end='')
for i in range(index_b, n):
	print('0', end='')


__author__ = 'asmn'
n = int(input())
a = sorted(((num, (j, i)) for i in range(n) for (j, num) in enumerate(map(int, input().split()))))
mk = [['0'] * n, ['0'] * n]
for (k, (num, (j, i))) in enumerate(a):
	if (i + 1) * 2 <= n or k + 1 <= n:
		mk[j][i] = '1'
print('\n'.join((''.join(ss) for ss in mk)))


def arr_2d(n):
	return [[int(x) for x in stdin.readline().split()] for i in range(n)]

def get_col(arr, i):
	return [row[i] for row in arr]
from sys import stdin
from collections import defaultdict
(n, ans1, ans2, mem) = (int(input()), [], [], defaultdict(int))
(a, all) = (arr_2d(n), [])
for i in range(n):
	(mem[a[i][0]], mem[a[i][1]]) = (1, 2)
	all.extend([a[i][0], a[i][1]])
all.sort()
for i in range(n):
	if mem[all[i]] == 1:
		ans1.append('1')
	else:
		ans2.append('1')
if len(ans1) < n // 2:
	ans1.extend(['1' for i in range(n // 2 - len(ans1))])
if len(ans2) < n // 2:
	ans2.extend(['1' for i in range(n // 2 - len(ans2))])
ans2.extend(['0' for i in range(n - len(ans2))])
ans1.extend(['0' for i in range(n - len(ans1))])
print(''.join(ans1), ''.join(ans2), sep='\n')


n = int(input())
teamA = [0] * n
teamB = [0] * n
for i in range(n):
	(teamA[i], teamB[i]) = map(int, input().split())
resultA = [0] * n
resultB = [0] * n
curA = 0
curB = 0
for i in range(n):
	if teamA[curA] < teamB[curB]:
		resultA[curA] = 1
		curA += 1
	else:
		resultB[curB] = 1
		curB += 1
for i in range(n // 2):
	resultA[i] = 1
	resultB[i] = 1
for i in range(n):
	print(resultA[i], end='')
print()
for i in range(n):
	print(resultB[i], end='')