"We've tried solitary confinement, waterboarding and listening to Just In Beaver, to no avail. We need something extreme."

"Little Alena got an array as a birthday present..."

The array b of length n is obtained from the array a of length n and two integers l and r (l ≤ r) using the following procedure:

b_1 = b_2 = b_3 = b_4 = 0.

For all 5 ≤ i ≤ n:   b_{i} = 0 if a_{i}, a_{i} - 1, a_{i} - 2, a_{i} - 3, a_{i} - 4 > r and b_{i} - 1 = b_{i} - 2 = b_{i} - 3 = b_{i} - 4 = 1  b_{i} = 1 if a_{i}, a_{i} - 1, a_{i} - 2, a_{i} - 3, a_{i} - 4 < l and b_{i} - 1 = b_{i} - 2 = b_{i} - 3 = b_{i} - 4 = 0  b_{i} = b_{i} - 1 otherwise 

You are given arrays a and b' of the same length. Find two integers l and r (l ≤ r), such that applying the algorithm described above will yield an array b equal to b'.

It's guaranteed that the answer exists.


-----Input-----

The first line of input contains a single integer n (5 ≤ n ≤ 10^5) — the length of a and b'.

The second line of input contains n space separated integers a_1, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the elements of a.

The third line of input contains a string of n characters, consisting of 0 and 1 — the elements of b'. Note that they are not separated by spaces.


-----Output-----

Output two integers l and r ( - 10^9 ≤ l ≤ r ≤ 10^9), conforming to the requirements described above.

If there are multiple solutions, output any of them.

It's guaranteed that the answer exists.


-----Examples-----
Input
5
1 2 3 4 5
00001

Output
6 15

Input
10
-10 -9 -8 -7 -6 6 7 8 9 10
0000111110

Output
-5 5



-----Note-----

In the first test case any pair of l and r pair is valid, if 6 ≤ l ≤ r ≤ 10^9, in that case b_5 = 1, because a_1, ..., a_5 < l.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
b = input()
r = 1000000000
l = -r
for i in range(4, n):
  if b[i - 1] != b[i]:
    if b[i] == '0':
      r = min(r, min(a[i - 4: i + 1]) - 1)
    else:
      l = max(l, max(a[i - 4: i + 1]) + 1)
print(l, r)


n = int(input())
a = list(map(int, input().split()))
b = input()
l = -(10**9)
r = 10**9
for i in range(4, n):
    if b[i] == '1' and b[i-4:i] == '0000':
        l = max(l, max([a[i],a[i-1], a[i-2], a[i-3], a[i-4]])+1)
    elif b[i] == '0' and b[i-4:i] == '1111':
        r = min(r, min([a[i],a[i-1], a[i-2], a[i-3], a[i-4]])-1)
print(l, r)

n = int(input())
a = [int(x) for x in input().split(' ')]
b = input()

llow = -1000000000
lhigh = 1000000000
rlow = -1000000000
rhigh = 1000000000

i = 4
last = 0
while i < n:
	if int(b[i]) == last:
		if last == 1:
			if min(a[i-4:i+1]) > rlow:
				rlow = min(a[i-4:i+1])
		else:
			if max(a[i-4:i+1]) < llow:
				lhigh = max(a[i-4:i+1])

		i+=1
	else:
		if last == 1:
			if min(a[i-4:i+1]) <= rhigh:
				rhigh = min(a[i-4:i+1]) - 1
		else:
			if max(a[i-4:i+1]) >= llow:
				llow = max(a[i-4:i+1]) +1

		last = 1-last
		i+=4

	if llow == lhigh and rlow == rhigh:
		break

print(str(llow)+' '+str(rhigh))

n=int(input())
a=list(map(int,input().split()))
s=input()
l=-1000000000
r=1000000000
for i in range(4,n):
    if s[i-4:i]=='0000':
        if s[i]=='1':
            l=max(max(a[i-4:i+1])+1,l)
    if s[i-4:i]=='1111':
        if s[i]=='0':
            r=min(min(a[i-4:i+1])-1,r)
print(l, r)
    


n = int(input())
a = list(map(int, input().split()))
b = list(map(lambda x: 1 if x == '1' else 0, input()))
left, right = - 10 ** 9, 10 ** 9
for i in range(4, n):
	test = True
	for j in range(2, 5):
		if b[i - j] != b[i - 1]:
			test = False
	if not test:
		continue
	if b[i] == 0 and b[i - 1] == 1:
		for j in range(5):
			right = min(right, a[i - j] - 1)
	if b[i] == 1 and b[i - 1] == 0:
		for j in range(5):
			left = max(left, a[i - j] + 1)
print(left, right)

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,list(input())))
current = 0
l = 10**9 * (-1)
r = 10**9
for i in range(n):
	if(b[i] != current):
		current = b[i]
		if(b[i] == 0):
			r = min(r, min(a[i-4:i+1])-1)
		else:
			l = max(l, max(a[i-4:i+1])+1)
print(l,r,end = " ")

from sys import stdin as cin

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = input()
    l, r = '?', '?'
    for i in range(1, n):
        if b[i] == '1' and b[i-1] == '0':
            if l == '?':
                l = 1 + max(a[i], a[i-1], a[i-2], a[i-3], a[i-4])
            else:
                l = max(l, 1 + max(a[i], a[i-1], a[i-2], a[i-3], a[i-4]))
        if b[i] == '0' and b[i-1] == '1':
            if r == '?':
                r = min(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) - 1
            else:
                r = min(r, min(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) - 1)
    if l == '?':
        l = -1000000000
    if r == '?':
        r = 1000000000
    print(l, r)

main()


def run():
    n = int(input())
    a = [int(x) for x in input().split()]
    bt = [int(x) for x in input()]

    lmin = -(10**9)
    lmax = -lmin
    rmin = lmin
    rmax = lmax

    for i in range(4, n):
        prev = bt[i-1] + bt[i-2] + bt[i-3] + bt[i-4]
        if 0 < prev < 4:
            continue

        if prev == 0:

            acmp = max((a[i], a[i-1], a[i-2], a[i-3], a[i-4]))
            if bt[i] == 1:
                lminc = acmp + 1
                lmin = lminc if lminc > lmin else lmin
            else:
                lmaxc = acmp
                lmax = lmaxc if lmaxc < lmax else lmax

        elif prev == 4:

            acmp = min((a[i], a[i-1], a[i-2], a[i-3], a[i-4]))
            if bt[i] == 0:
                rmaxc = acmp - 1
                rmax = rmaxc if rmaxc < rmax else rmax
            else:
                rminc = acmp
                rmin = rminc if rminc > rmin else rmin

    print(f'{lmin} {rmax}')

run()

_ = input()
numbers = [int(x) for x in input().split()]
bits = input()

INF = int(1e9)

lowerBoundL = -INF
upperBoundL = INF
lowerBoundR = -INF
upperBoundR = INF

for pos in range(4, len(bits)):
	window = slice(pos - 4, pos + 1)

	if bits[window] == '00000':
		upperBoundL = min(upperBoundL, *numbers[window])
	elif bits[window] == '00001':
		lowerBoundL = max(lowerBoundL, *(x + 1 for x in numbers[window]))
	elif bits[window] == '11111':
		lowerBoundR = max(lowerBoundR, *numbers[window])
	elif bits[window] == '11110':
		upperBoundR = min(upperBoundR, *(x - 1 for x in numbers[window]))

print(lowerBoundL, upperBoundR)

n = int(input())
a = input().split()
b = input()
_b = list()

for i in range(len(a)):
    a[i] = int(a[i])

for l in b:
    _b.append(int(l))

b = _b
r = 10**9
l = -10**9

for i in range(len(b)):
    if i > 3:
        if b[i] == 0 and b[i-1] == b[i-2] == b[i-3] == b[i-4] == 1:
            if min(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) - 1 < r:
                r = min(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) - 1
        elif b[i] == 1 and b[i-1] == b[i-2] == b[i-3] == b[i-4] == 0:
            if max(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) + 1 > l:
                l = max(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) + 1

print(l, r)


inf = int(1e9)
M = mod = 1000000007
mod2inv = 500000004
pt = lambda *a, **k: print(*a, **k, flush=True)
rd = lambda: map(int, input().split())
n = int(input())
a = list(rd())
b = input()
l1 = -inf
l2 = inf
r1 = -inf
r2 = inf
f = 4
for i in range(4, n):
    x = b[i]
    if f == 4 and x == '1':
        l1 = max(l1, max(a[i - 4: i + 1]) + 1)
        f = 0
    if f == 4 and x == '0':
        l2 = min(l2, max(a[i - 4: i + 1]))
    if f == -4 and x == '1':
        r1 = max(r1, min(a[i - 4: i + 1]))
    if f == -4 and x == '0':
        r2 = min(r2, min(a[i - 4: i + 1]) - 1)
        f = 0
    if -4 < f < 4:
        if x == '0':
            f += 1
        if x == '1':
            f -= 1
print(min(l1, l2), max(r1, r2))


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

r = 1e+9
l = -1e+9

for i in range(4, n):
    if b[i - 4: i] == "1111" and b[i] == "0":
        r = min(r, min(a[i - 4: i + 1]) - 1)
    if b[i - 4: i] == "0000" and b[i] == "1":
        l = max(l, max(a[i - 4: i + 1]) + 1)

print(int(l), int(r))


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, list(input())))

    # print(A, B)

    LMIN = -10**9
    LMAX = 10**9
    RMIN = -10**9
    RMAX = 10**9
    for i in range(4, n):
        if b[i-1] == 0 and b[i-2] == 0 and b[i-3] == 0 and b[i-4] == 0:
            if b[i] == 1:
                LMIN = max(LMIN, max(a[i],a[i-1],a[i-2],a[i-3],a[i-4])+1)
            elif b[i] == 0:
                LMAX = min(LMAX, max(a[i],a[i-1],a[i-2],a[i-3],a[i-4]))
        elif b[i-1] == 1 and b[i-2] == 1 and b[i-3] == 1 and b[i-4] == 1:
            if b[i] == 1:
                RMIN = max(RMIN, min(a[i],a[i-1],a[i-2],a[i-3],a[i-4]))
            elif b[i] == 0:
                RMAX = min(RMAX, min(a[i],a[i-1],a[i-2],a[i-3],a[i-4])-1)
        else:
            pass

    # print(LMIN, LMAX, RMIN, RMAX)

    # l = (LMIN + LMAX)//2

    print(LMIN, RMAX)

def __starting_point():
    solve()



__starting_point()

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

l, r = -10 ** 9, 10 ** 9

for i, el in enumerate(b[4:], 4):
    if b[i - 4: i] == '0000' and el == '1':
        l = max(l, max(a[i - 4: i + 1]) + 1)

    elif b[i - 4: i] == '1111' and el == '0':
        r = min(r, min(a[i - 4: i + 1]) - 1)

print(l, r)


def check(lst, val):
    return (lst[1:] == lst[:-1]) and (lst[0] == val)
n = int(input())
a= [int(s) for s in input().split(" ")]
b_= [int(s) for s in list(input())]
l = -10**9
r = 10**9
list_=b_[:4]
for i in range(4, len(b_)):
    if  check(list_,0):
        if b_[i] == 1:
            l = max(max(a[i-4:i+1]) + 1,l)
    elif check(list_,1):
        if b_[i] == 0:
            r = min(r,min(a[i-4:i+1]) - 1)
    list_.pop(0)
    list_.insert(len(list_),b_[i])

print(str(l)+ " " + str(r))



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

minl = int(-1e9)
maxr = int(1e9)

for i in range(4, n):
  if not (b[i-4] == b[i-3] == b[i-2] == b[i-1] != b[i]):
    continue
  #print('working for', i)
  if b[i] == '0':
    maxr = min(maxr+1, a[i], a[i-1], a[i-2], a[i-3], a[i-4])-1
  if b[i] == '1':
    minl = max(minl-1, a[i], a[i-1], a[i-2], a[i-3], a[i-4])+1

print(minl, maxr)

import re
input()
a = list(map(int, input().split()))
b = input()
l, r = -10**9, 10**9

# a: a a a a a > r
# b: 1 1 1 1 0
for m in re.finditer("11110", b):
	i = m.start(0)
	r = min([r + 1] + a[i:i+5]) - 1

# a: a a a a a < l
# b: 0 0 0 0 1 		
for m in re.finditer("00001", b):
	i = m.start(0)
	l = max([l - 1] + a[i:i+5]) + 1
		
print(l, r)

3

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input()))
l = None
r = None
i = 4
while i < n:
	if b[i] == 0 and b[i-1] == b[i-2] == b[i-3] == b[i-4] == 1:
		if r is None:
			r = min(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) - 1
		else:
			r = min(r, min(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) - 1)
	elif b[i] == 1 and b[i-1] == b[i-2] == b[i-3] == b[i-4] == 0:
		if l is None:
			l = max(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) + 1
		else:
			l = max(l, max(a[i], a[i-1], a[i-2], a[i-3], a[i-4]) + 1)
	i += 1

if l is None:
	l = -1000000000
if r is None:
	r = 1000000000
print("%s %s" % (l, r))

n = int(input())
ls = list(map(int, input().split()))
s = input()
r = int(1e9)
l = -r
i = 4
while i < n:
    if s[i] == s[i - 1]: 
        i += 1
        continue
    if s[i] == '1': 
        l = max(l, max(ls[i - 4 : i + 1]) + 1)
    elif s[i] == '0':
        r = min(r, min(ls[i - 4 : i + 1]) - 1)
    i += 1
print(l, r)





def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    b = input()

    re = int(1e9)
    le = -re
    x = True
    for i in range(n):
        if b[i] == ('1' if x else '0'):
            for j in a[i - 4:i + 1]:
                if x:
                    if le <= j:
                        le = j + 1
                else:
                    if re >= j:
                        re = j - 1
            x = not x
    print(le, re)


def __starting_point():
    main()

__starting_point()