You are given a string $s$ consisting of $n$ characters. Each character of $s$ is either 0 or 1.

A substring of $s$ is a contiguous subsequence of its characters.

You have to choose two substrings of $s$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:

let $s_1$ be the first substring, $s_2$ be the second chosen substring, and $f(s_i)$ be the integer such that $s_i$ is its binary representation (for example, if $s_i$ is 11010, $f(s_i) = 26$);

the value is the bitwise OR of $f(s_1)$ and $f(s_2)$.

Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.


-----Input-----

The first line contains one integer $n$ — the number of characters in $s$.

The second line contains $s$ itself, consisting of exactly $n$ characters 0 and/or 1.

All non-example tests in this problem are generated randomly: every character of $s$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $\frac{1}{2}$.

This problem has exactly $40$ tests. Tests from $1$ to $3$ are the examples; tests from $4$ to $40$ are generated randomly. In tests from $4$ to $10$, $n = 5$; in tests from $11$ to $20$, $n = 1000$; in tests from $21$ to $40$, $n = 10^6$.

Hacks are forbidden in this problem.


-----Output-----

Print the maximum possible value you can get in binary representation without leading zeroes.


-----Examples-----

Input
5
11010
Output
11111
Input
7
1110010
Output
1111110
Input
4
0000
Output
0


-----Note-----

In the first example, you can choose the substrings 11010 and 101. $f(s_1) = 26$, $f(s_2) = 5$, their bitwise OR is $31$, and the binary representation of $31$ is 11111.

In the second example, you can choose the substrings 1110010 and 11100.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Dynamic programming

Complete search

Probability
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
n = int(input())
s = input()
first1 = n
for i in range(len(s)):
	if s[i] == '1':
		first1 = i
		break
s = s[first1:]
if s == '':
	print(0)
else:
	first0 = n
	for i in range(len(s)):
		if s[i] == '0':
			first0 = i
			break
	if first0 == n:
		print(s)
	else:
		n = int(s, 2)
		best = n
		for i in range(first0 + 1):
			best = max(best, n | n >> i)
		print(bin(best)[2:])
print()


n = int(input())
s = int(input(), 2)
ans = 0
for i in range(20):
	ans = max(ans, s | s >> i)
ans = bin(ans)
ans = ans[2:]
print(ans)


input()
n = int(input(), 2)
m = n
for i in range(1, 9):
	m = max(m, n | n >> i)
print(bin(m)[2:])


n = int(input())
s = input()
b = int(s, 2)
a = b
mx = a | b
for i in range(0, 7):
	a = a >> 1
	m = a | b
	if m > mx:
		mx = m
st = format(mx, 'b')
print(st)


input()
n = int(input(), 2)
m = n
for i in range(1, 9):
	m = max(m, n | n >> i)
print('{0:b}'.format(m))


lenght = input()
n = int(input(), 2)
rez = 0
for i in range(10):
	rez = max(rez, n | n >> i)
print(bin(rez)[2:])


n = int(input())
a = int(input(), 2)
temp = a
mx = a | temp
for i in range(7):
	temp = temp >> 1
	m = a | temp
	if mx < m:
		mx = m
print(bin(mx).replace('0b', ''))


n = input()
s = x = int(input(), 2)
for i in range(8):
	x = max(x, s | s >> i)
print(bin(x)[2:])


n = int(input())
s = input()
if s.count('0') == n:
	print('0')
elif s.count('1') == n:
	print(s)
else:
	s = s.lstrip('0')
	n = len(s)
	a = int(s, 2)
	p = s.index('0')
	k = n - p
	ans = 0
	for i in range(n - k):
		sk = s[i:i + k]
		b = int(sk, 2)
		ans = max(a | b, ans)
	ans = bin(ans)
	ans = ans[2:]
	ans = ans.lstrip('0')
	print(ans)


from sys import exit
n = int(input())
s = input()
f1 = s.find('1')
if f1 == -1:
	print(0)
	exit()
ln = 0
for i in range(f1, n):
	if s[i] == '1':
		ln += 1
	else:
		break
sb = int(s, 2)
res = sb
for i in range(ln):
	res = max(res, sb | int(s[:-(i + 1)], 2))
print(bin(res)[2:])


l = int(input())
n = int(input(), 2)
m = n
for i in range(1, 50):
	m = max(m, n | n >> i)
print(bin(m)[2:])


input()
n = int(input(), 2)
maks = n
for i in range(1, 20):
	maks = max(maks, n | n >> i)
print(bin(maks)[2:])


len_1 = int(input())
str_1 = input()
msb = -1
flag = 0
for t in range(len_1):
	if str_1[t] == '0':
		msb = t
		if flag == 1:
			break
	if str_1[t] == '1':
		flag = 1
seg_len = len_1 - msb
lst_val = []
u = 0
while seg_len + u <= len_1:
	lst_val.append(int(str_1[u:seg_len + u], 2))
	u += 1
val = int(str_1, 2)
max = val
for t in lst_val:
	if val | t > max:
		max = t | val
bin_2 = bin(max)
print(bin_2[2:])


input()
ash = int(input(), 2)
m = ash
for i in range(1, 100):
	m = max(m, ash | ash >> i)
print('{0:b}'.format(m))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	S = input().strip()
	if S == '1' * n:
		return S
	elif S == '0' * n:
		return '0'
	m = st1 = 0
	ans = 0
	for i in range(n - 1):
		if st1 == 0 and S[i] == '1':
			st1 = S[i:]
			st1 = int(st1, 2)
		if S[i] == '1' and S[i + 1] == '0':
			k = n - (i + 1)
			for j in range(i, -1, -1):
				if S[j] == '0':
					continue
				st2 = S[j:]
				st2 = st2[:k]
				ans = max(ans, st1 | int(st2, 2))
			return bin(ans)[2:]
print(solve())


def valOf(inp):
	return int(inp, base=2)

def mainFunc():
	n = int(input())
	s = input()
	s = s.lstrip('0')
	if not s:
		print(0)
		return
	zeroPos = -1
	for (index, value) in enumerate(s):
		if value == '0':
			zeroPos = index
			break
	if zeroPos == -1:
		print(s)
		return
	expectedS2Size = len(s) - zeroPos
	maxOrPossible = valOf(s)
	for i in range(0, len(s) - expectedS2Size):
		maxOrPossible = max(maxOrPossible, valOf(s[i:i + expectedS2Size]) | valOf(s))
	print(bin(maxOrPossible).replace('0b', ''))
	return
t = 1
for testcase in range(t):
	mainFunc()


import math
n = int(input())
s = input()
ans = int(s, 2)
for i in range(1, 11):
	ps = s[0:n - i]
	if len(ps) == 0:
		break
	pans = int(ps, 2) | int(s, 2)
	ans = max(ans, pans)
print(bin(ans)[2:])


from sys import stdin, stdout

def ss(n, s):
	if s.count('0') == n:
		return '0'
	y = int(s, 2)
	s = bin(y)[2:]
	l = ''
	if y == 0:
		return '0'
	for t in range(len(s)):
		i = s[t]
		if i == '0':
			l += '1'
		elif l != '':
			l += '0'
	mx = 0
	m = len(l)
	if l:
		for j in range(n - m):
			mx = max(mx, y | int(s[j:j + m], 2))
	else:
		mx = y or int(s[-1], 2)
	return bin(mx)[2:]
n = int(input())
s = input()
print(ss(n, s))


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]
n = ni()
a = INP()
if a.count('1') == 0:
	print(0)
else:
	f = False
	f0 = False
	first = 0
	f0i = 0
	for i in range(n):
		if a[i] == '1':
			if not f:
				f = True
				first = i
		if f:
			if a[i] == '0':
				if not f0:
					f0 = True
					f0i = i
	l = n - f0i
	org = int(a[first:], 2)
	best = int(a[first:], 2)
	for i in range(n - l + 1):
		best = max(best, org | int(a[i:i + l], 2))
	print(bin(best)[2:])


n = int(input())
s = input()
y = int(s, 2)
s = bin(y)[2:]
l = ''
if y == 0:
	print('0')
else:
	for i in s:
		if i == '0':
			l += '1'
		elif l != '':
			l += '0'
	mx = 0
	m = len(l)
	if m == 0:
		mx = y or int(s[-1], 2)
	else:
		for j in range(n - m):
			mx = max(mx, y | int(s[j:j + m], 2))
	print(bin(mx)[2:])


n = int(input())
s = input()
s = list(s)
i = 0
while s[i] == '0':
	i += 1
	if i == n:
		break
if i == n:
	print(0)
else:
	s = s[i:]
	n = len(s)
	ans = [i for i in s]
	i = 0
	o = 0
	while s[i] == '1':
		o += 1
		i += 1
	if o == 0:
		print('0')
	else:
		ones = [j for j in range(1, o + 1)]
		while i < n and len(ones) > 0:
			if s[i] == '0':
				tmp = []
				for j in ones:
					if s[i - j] == '1':
						tmp.append(j)
				if len(tmp) > 0:
					ans[i] = '1'
					ones = tmp
			i += 1
		anss = ''
		for i in ans:
			anss += i
		print(anss)


n = int(input())
s = input()
i = s.find('1')
if i == -1:
	print(0)
else:
	s1 = s[i:]
	j = s1.find('0')
	if j == -1:
		print(s1)
	else:
		s2 = s1[j:]
		s3 = s1[:j] + ''.join((str(int(a) or int(b)) for (a, b) in zip(s1, s2)))
		s2 = s1[1:]
		s4 = s1[:1] + ''.join((str(int(a) or int(b)) for (a, b) in zip(s1, s2)))
		print(max(s3, s4))


import itertools
from math import floor, log, log2, ceil, sqrt
from itertools import groupby
from decimal import Decimal, getcontext
from posixpath import split
import sys
from collections import deque
primes = set()
maxN = 1000001

def generatePrimes():
	used = [False] * maxN
	for i in range(2, maxN):
		if not used[i]:
			primes.add(i)
			for j in range(i, maxN, i):
				used[j] = True

def isPrime(n):
	if n < 2:
		return True
	x = 2
	while x * x <= n:
		if n % x == 0:
			return False
		x += 1
	return True

def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x

def solve():
	n = int(input())
	s = input()
	index = 0
	while index < n and s[index] == '0':
		index += 1
	if index == n:
		print(0)
		return
	s = s[index:]
	n -= index
	k = 0
	while k < n and s[k] == '1':
		k += 1
	if k == n:
		print(s)
		return
	res = s
	for i in range(k):
		temp = list(s)
		for j in range(k, n):
			if temp[j] == '0':
				temp[j] = '1' if s[j - k + i] == '1' else '0'
		res = max(res, ''.join(temp))
	print(res)
solve()


n = int(input())
binary = input()
binary = binary.lstrip('0')
n = len(binary)
p_zero = []
p_one = []
for i in range(n):
	if binary[i] == '0':
		p_zero.append(i)
	else:
		p_one.append(i)
if len(p_one) == 0:
	print(0)
elif len(p_zero) == 0:
	print(binary)
else:
	size = n - p_zero[0]
	max_sub = ''
	seq = ''
	for i in p_one:
		if n - i < size:
			break
		sub = binary[i:i + size]
		if i == p_one[0]:
			for j in p_zero:
				if sub[j - p_zero[0]] == '1':
					seq += '1'
				else:
					seq += '0'
			max_sub = sub
		else:
			p = 0
			c_seq = ''
			flag = True
			for j in p_zero:
				if sub[j - p_zero[0]] == '1':
					c_seq += '1'
				else:
					c_seq += '0'
				if seq[p] < c_seq[-1]:
					break
				if seq[p] > c_seq[-1]:
					flag = False
					break
				p += 1
			if flag:
				seq = c_seq
				max_sub = sub
	max_sub = '0' * (n - size) + max_sub
	for i in range(n):
		print('1' if binary[i] == '1' or max_sub[i] == '1' else '0', end='')
	print()


def sor(s1: str, s2: str):
	a1 = list(max(s1, s2))
	a2 = min(s1, s2)
	for i in range(len(a2)):
		if a2[i] == '1':
			a1[len(a1) - len(a2) + i] = '1'
	return ''.join(a1).lstrip('0')
n = int(input())
s = input().lstrip('0')
n = len(s)
ans = '0'
a1 = s.find('1')
if a1 != -1:
	a2 = s.find('0')
	if a2 != -1:
		for i in range(a1, a2):
			l = n - a2
			s2 = s[i:i + l]
			ans = max(ans, sor(s, s2))
print(ans)


import sys
import threading
from functools import lru_cache
from bisect import bisect_left
from collections import defaultdict, deque
from heapq import *

def main():
	n = int(input())
	s = input()
	s = list(s)
	while s and s[0] == '0':
		del s[0]
	ans = [i for i in s]
	firstZero = -1
	firstOne = -1
	for index in range(len(s)):
		if s[index] == '1' and firstOne == -1:
			firstOne = index
		if s[index] == '0' and firstZero == -1:
			firstZero = index
	if firstOne == -1 or firstZero == -1:
		print(''.join(ans) if ans else '0')
		exit(0)
	for index in range(0, firstZero):
		curr = list(s[:firstZero])
		current_index = index
		for j in range(firstZero, len(s)):
			if s[current_index] == '1':
				curr.append('1')
			else:
				curr.append(s[j])
			current_index += 1
		rep = False
		for m in range(len(s)):
			if curr[m] == '1' and ans[m] == '0':
				rep = True
				break
			if curr[m] == '0' and ans[m] == '1':
				break
		if rep:
			ans = curr
	print(''.join(ans))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


n = int(input())
s = input()
ind = []
index = 0
flag = 0
len_index = 0
ed = 0
for i in range(n):
	if flag:
		index += 1
	if s[i] == '1':
		ed = 1
	if s[i] == '0' and ed != 0:
		ind.append(index)
		flag = 1
		len_index += 1
if flag == 0:
	print(0)
	exit(0)
ln = index
mx_s = ''
for i in range(ln, n):
	new_s = ''
	for j in ind:
		new_s += s[i - (ln - j)]
	if new_s > mx_s:
		mx_s = new_s
ans = ['0'] * (ln + 1)
for i in range(len_index):
	ans[ind[i]] = mx_s[i]
ans = ''.join(ans)
ans = int(ans, 2) | int(s, 2)
print(bin(ans)[2:])


n = int(input())
ss = input()

def cal(s):
	if '1' not in s:
		return '0'
	s = s[s.index('1'):]
	if '0' not in s:
		return s[:-1] + '0'
	t = s[s.index('0'):]
	k = len(t)
	re = t
	for i in range(len(s) - k + 1):
		if s[i] != '1':
			continue
		p = s[i:i + k]
		c = [max(p[j], t[j]) for j in range(k)]
		ck = ''.join(c)
		if ck == '1' * k:
			return '1' * len(s)
		re = max(re, ck)
	return s[:-k] + re
print(cal(ss))


n = int(input())
s = [int(x) for x in list(input())]
if sum(s) == 0:
	print(0)
else:
	leadingOnes = 0
	s1 = []
	stop = False
	for i in range(n):
		if not stop:
			if s[i] == 1:
				leadingOnes += 1
			if s[i] == 0 and leadingOnes > 0:
				stop = True
		if leadingOnes > 0:
			s1.append(s[i])
	best = s1
	for i in range(leadingOnes + 1):
		s2 = [0 for _ in range(i + 1)] + s1[:len(s1) - i + 1]
		isBetter = False
		new = []
		for i in range(len(s1)):
			if not (s2[i] == 1 or s1[i] == 1) and (best[i] == 1 or s1[i] == 1) and (not isBetter):
				break
			if s2[i] == 1 or s1[i] == 1:
				if best[i] == 0:
					isBetter = True
				new.append(1)
			else:
				new.append(0)
		if isBetter:
			best = new
	print(''.join(map(str, best)))


from sys import stdin, setrecursionlimit
input = stdin.readline
import heapq
rd = lambda : map(lambda s: int(s), input().strip().split())
rdone = lambda : map(lambda s: int(s) - 1, input().strip().split())
ri = lambda : int(input())
rs = lambda : input().strip()
from collections import defaultdict as unsafedict, deque, Counter as unsafecounter
from bisect import bisect_left as bl, bisect_right as br
from random import randint
from math import gcd, floor, log2, factorial, radians, sin, cos, ceil
n = ri()
s = rs()
z = []
o = []
for i in range(len(s)):
	if s[i] == '0':
		z.append(i)
	else:
		o.append(i)
r = []
val = -1
for i in z:
	if o and o[0] < i:
		while o and o[0] < i:
			r.append(o.pop(0))
		val = i
		break
if val == -1:
	s = s.lstrip('0')
	if s == '':
		s = '0'
	print(s)
	exit()
l = n - val
pp = []
mx = s
for i in r:
	res = s[i:i + l]
	st = list(s)
	base = 0
	for ind in range(val, n):
		if s[ind] == '0' and res[base] == '1':
			st[ind] = '1'
		base += 1
	mx = max(mx, ''.join(st))
print(mx.lstrip('0'))


def main():
	n = int(input())
	s = list(input())
	i = 0
	while i < n and s[i] == '0':
		i += 1
	if i == n:
		s = '0'
	else:
		s = s[i:]
	n = len(s)
	pos = -1
	for i in range(n):
		if s[i] == '0':
			pos = i
			break
	if pos == -1:
		print(''.join(s))
		return
	if pos == 0:
		print(0)
		return
	ans = []
	for i in range(pos):
		t = s[i:i + (n - pos)]
		(j, k) = (len(s) - 1, len(t) - 1)
		res = []
		while j >= 0 and k >= 0:
			res.append('1' if s[j] == '1' or t[k] == '1' else '0')
			j -= 1
			k -= 1
		while j >= 0:
			res.append(s[j])
			j -= 1
		res.reverse()
		ans.append(''.join(res))
	ans.sort(reverse=True)
	i = 0
	while i < n and ans[0][i] == '0':
		i += 1
	if i == n:
		print(0)
		return
	print(ans[0][i:])
main()


from copy import deepcopy
n = int(input())
s = input()
first_one = 0
while first_one < n and s[first_one] == '0':
	first_one += 1
s = s[first_one:]
n -= first_one
cnt_of_ones = 0
while cnt_of_ones < n and s[cnt_of_ones] != '0':
	cnt_of_ones += 1
s_max = ''
for i in range(cnt_of_ones + 1):
	s_ = ''
	si = ''
	for j in range(i):
		s_ += '0'
	s_ += s[0:n - i]
	for j in range(n):
		if s[j] == '1' or s_[j] == '1':
			si += '1'
		else:
			si += '0'
	s_max = max(s_max, si)
if s_max != '':
	print(s_max)
else:
	print('0')


def getStr(i, k):
	ans = ''
	while i < n:
		if s[i] == '1' or s[k] == '1':
			ans += '1'
		else:
			ans += '0'
		i += 1
		k += 1
	return ans
n = int(input())
s = input()
i = 0
while i < n and s[i] == '0':
	i += 1
if i == n:
	print(0)
	exit()
j = i
while i < n and s[i] == '1':
	i += 1
ans = '0' * (n - i - j)
for k in range(i, j - 1, -1):
	t = getStr(i, k)
	ans = max(ans, t)
print(s[j:i] + ans)


def solve1(n, o, s):
	p = ''
	flag = False
	for i in range(0, n):
		if s[i] == '1' or flag:
			flag = True
			p += s[i]
	if len(p) == 0:
		print(0)
		exit(0)
	s = p
	n = len(s)
	p = ''
	for i in range(2, n + 1):
		x = n - o + 1
		y = n - i + 1
		for j in range(min(x, y), n + 1):
			if s[j - 1] == '0':
				if j >= x:
					a = s[j - x] == '1'
				else:
					a = 0
				if j >= y:
					b = s[j - y] == '1'
				else:
					b = 0
				if a < b:
					o = i
				if a != b:
					break
	for i in range(1, n + 1):
		p += str(((i >= n - o + 1 and s[i - n + o - 1] == '1') | int(s[i - 1]) - 48) + 48)
	print(p)
(n, o) = [int(input()), 1]
s = input()
solve1(n, o, s)
while None:
	pass
while 1:
	break


import sys
input = sys.stdin.readline

def pobit(s, s2):
	i = len(s) - 1
	l = len(s2) - 1
	ans = []
	while l >= 0:
		if s[i] == '1' or s2[l] == '1':
			ans.append('1')
		else:
			ans.append('0')
		i -= 1
		l -= 1
	while i >= 0:
		ans.append(str(s[i]))
		i -= 1
	stroka = ''
	i = len(s) - 1
	while ans[i] == '0':
		i -= 1
		if i == 0:
			break
	while i >= 0:
		stroka += ans[i]
		i -= 1
	return stroka

def solve():
	n = int(input())
	s = input()
	s = s[0:n]
	x = 0
	i = 0
	while s[i] == '0':
		i += 1
		if i == n:
			return '0'
	while i < n:
		if s[i] == '1':
			x += 1
		else:
			break
		i += 1
	ans = '0'
	for i in range(n - x, n):
		y = pobit(s, s[0:i])
		if y > ans:
			ans = y
	return ans
ans = solve()
print(ans)


import sys
input = sys.stdin.readline

def pobit(S, S1):
	i = len(S) - 1
	l = len(S1) - 1
	answer = []
	while l >= 0:
		if S[i] == '1' or S1[l] == '1':
			answer.append('1')
		else:
			answer.append('0')
		i -= 1
		l -= 1
	while i >= 0:
		answer.append(str(S[i]))
		i -= 1
	stroka = ''
	i = len(S) - 1
	while answer[i] == '0':
		i -= 1
		if i == 0:
			break
	while i >= 0:
		stroka += answer[i]
		i -= 1
	return stroka

def solve():
	n = int(input())
	S = input()
	S = S[0:n]
	x = 0
	i = 0
	while S[i] == '0':
		i += 1
		if i == n:
			return '0'
	while i < n:
		if S[i] == '1':
			x += 1
		else:
			break
		i += 1
	answer = '0'
	for i in range(n - x, n):
		y = pobit(S, S[0:i])
		if y > answer:
			answer = y
	return answer
answer = solve()
print(answer)


def update(s, i, j, n, mx):
	while j >= i:
		s[n - 1] |= s[j]
		j -= 1
		n -= 1
	mx = max(mx, s)
	return mx

def solve():
	n = int(input())
	s = input().strip()
	s = [int(el) for el in s]
	i = 0
	while i < n and s[i] == 0:
		i += 1
	if i == n:
		print(0)
		return
	s = s[i:]
	n = len(s)
	i = 0
	while i < n and s[i] == 1:
		i += 1
	if i == n:
		print(*s, sep='')
		return
	nt = n - i
	i = 0
	mx = [0] * nt
	while i + nt <= n:
		j = i + nt - 1
		mx = update(s.copy(), i, j, n, mx)
		i += 1
	i = 0
	while i < len(mx) - 1 and mx[i] == 0:
		i += 1
	print(*mx[i:], sep='')
solve()