Dima worked all day and wrote down on a long paper strip his favorite number $n$ consisting of $l$ digits. Unfortunately, the strip turned out to be so long that it didn't fit in the Dima's bookshelf.

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.


-----Input-----

The first line contains a single integer $l$ ($2 \le l \le 100\,000$) — the length of the Dima's favorite number.

The second line contains the positive integer $n$ initially written on the strip: the Dima's favorite number.

The integer $n$ consists of exactly $l$ digits and it does not contain leading zeros. Dima guarantees, that there is at least one valid way to split the strip.


-----Output-----

Print a single integer — the smallest number Dima can obtain.


-----Examples-----
Input
7
1234567

Output
1801

Input
3
101

Output
11



-----Note-----

In the first example Dima can split the number $1234567$ into integers $1234$ and $567$. Their sum is $1801$.

In the second example Dima can split the number $101$ into integers $10$ and $1$. Their sum is $11$. Note that it is impossible to split the strip into "1" and "01" since the numbers can't start with zeros.

Difficulty: interview

Starter code:

Solutions:
l = int(input())
n = input()
best = int(n)
p = (l - 1) // 2
for i in range(p, -1, -1):
	if (n[i + 1] == '0'):
		continue

	best = min(best, int(n[0:(i + 1)]) + int(n[i + 1:]))
	break

p = l // 2
for i in range(p, l):
	if (n[i] == '0'):
		continue

	best = min(best, int(n[0:i]) + int(n[i:]))
	break

print(best)

def f(R):
	if R==0:
		return 0
	F=0;S=0;cur=1
	for i in range(150):
		t=min(cur,R-F-S)
		#print(str(i)+' '+str(F)+' '+str(S)+' '+str(t))
		if i%2==0:
			F=F+t
		else:
			S=S+t
		cur=cur*2
		if R==F+S:
			break
	ans=F*F+S*S+S
	return ans

#L,R = map(int,input().strip().split())
#L = L-1
#ans = f(R)-f(L)
#ans = ans%1000000007
#print(ans)

import math


n=int(input())
s=input()
ans=int(s)
for i in range(n//2,n):
        if s[i]!='0':
                a=int(s[:i])
                b=int(s[i:])
                ans=min(ans,a+b)
                break
for i in range(n//2,0,-1):
        if s[i]!='0':
                a=int(s[:i])
                b=int(s[i:])
                ans=min(ans,a+b)
                break
for i in range(n//2+1,n):
        if s[i]!='0':
                a=int(s[:i])
                b=int(s[i:])
                ans=min(ans,a+b)
                break
for i in range(n//2+1,0,-1):
        if s[i]!='0':
                a=int(s[:i])
                b=int(s[i:])
                ans=min(ans,a+b)
                break
print(ans)
##V=[1]
##it=1
##den=1
##flag=0
##x=0
##for i in range(N):
##    s=input()
##    s+=" last"
##    s=s.strip().split()
##    if s[0]=="for":
##        n=int(s[1].strip())
##        if it>2**32:
##            n=1
##        it*=n
##        V.append(n)
##    elif s[0]=="add":
##        x+=it
##        if x>=2**32:
##            flag=1
##            break
##    elif s[0]=="end":
##        it/=V[-1]
##        V.pop()
##    #print(str(s)+" "+str(x)+" "+str(it)+" "+str(V))
##if flag==1:
##    print("OVERFLOW!!!")
##else:
##    print(int(x))
##t=[1]
##while t[len(t)-1]*2<=n:
##	t.append(t[-1]*2)
##x=0
##i=0
##while i<len(t) and x+t[i]<=n:
##	x=x+t[i]
##	i=i+1
##
##if n&(n+1)==0:
##	print n
##elif k==1:
##	print n
##else:
##	print 2*t[-1]-1


l = int(input())
s = input()

best = 0
best2 = None
for sl in range(1, l):
    if s[sl] != '0':
        if max(sl, l - sl) < max(best, l - best):
            best = sl
            best2 = None
        elif max(sl, l - sl) == max(best, l - best):
            best2 = sl

f = s[:best]
b = s[best:]

res = int(s[:best]) + int(s[best:])
if best2 is None:
    print(res)
else:
    res2 = int(s[:best2]) + int(s[best2:])
    print(min(res, res2))


n = int(input())
s = input()
ans = 10**(10**5 + 1)
i = n // 2 + 1
while i < n and s[i] == '0':
    i += 1
if i < n:
    ans = min(ans, int(s[:i]) + int(s[i:]))
i = n // 2
while s[i] == '0':
    i -= 1
if i > 0:
    ans = min(ans, int(s[:i]) + int(s[i:]))
print(ans)

len = int(input())
s = input()

ans = int(s)

for i in range((len - 1) // 2, 0, -1):
    if s[i] != '0':
        ans = min(ans, int(s[:i]) + int(s[i:]))
        break


for i in range(len // 2 + 1, len):
    if s[i] != '0':
        ans = min(ans, int(s[:i]) + int(s[i:]))
        break

if len % 2 == 0 and s[len // 2] != '0':
	i = len // 2
	ans = min(ans, int(s[:i]) + int(s[i:]))

print(ans)

def do(s, j):
    return int(s[:j]) + int(s[j:])


def main():
    n = int(input())
    x = input()
    mid = n // 2
    cnt = 0
    best = None
    for i in range(mid + 2):
        j = mid + i
        if j < n and x[j] != '0':
            val = do(x, j)
            cnt += 1
            if best is None:
                best = val
            else:
                best = min(best, val)
        
        j = mid - i
        if j > 0 and x[j] != '0':
            val = do(x, j)
            cnt += 1
            if best is None:
                best = val
            else:
                best = min(best, val)

        if cnt >= 7:
            break
    print(best)


def __starting_point():
    main()


__starting_point()

n = int(input())
s = input()
l = int(n / 2)
r = int((n + 1) / 2)
while (l and s[l] == '0'):
    l -= 1
while (r != n - 1 and s[r] == '0'):
    r += 1
if (l == 0 or r == n - 1):
    if (l == 0):
        ans = int(s[:r]) + int(s[r:])
    else:
        ans = int(s[:l]) + int(s[l:])
else:
    ans = min(int(s[:l]) + int(s[l:]), int(s[:r]) + int(s[r:]))
print(ans)

n = int(input())
s = input()
a = [i for i in range(1, n) if s[i] != '0']
a.sort(key=lambda i: abs(i - n / 2))
ans = float("inf")
for i in a[:6]:
  ans = min(ans, int(s[:i]) + int(s[i:]))
print(ans)


L = int(input())
X = input()

ans = float('inf')
cnt = 0
idx = L // 2

while cnt < 5 and idx >= 1:
    if X[idx] != '0':
        ans = min(ans, int(X[:idx]) + int(X[idx:]))
        cnt += 1
    idx -= 1

cnt = 0
idx = L // 2

while cnt < 5 and idx < L:
    if X[idx] != '0':
        ans = min(ans, int(X[:idx]) + int(X[idx:]))
        cnt += 1
    idx += 1

print(ans)

l = int(input())
n = str(input())
best_len = l
best = int(n)
to_try = []
for i in range(l - 1):
    if n[i + 1] != '0':
        candidate = max(i + 1, l - i - 1) + 1
        if candidate < best_len:
            to_try.clear()
            to_try.append(i+1)
            best_len = candidate
        elif candidate == best_len:
            to_try.append(i+1)
for i in to_try:
    best = min(best, int(n[:i]) + int(n[i:]))
print(best)

n = int(input())
a = input()

pos = n // 2

ans = -1

for it in range(n // 2, n // 2 - 5, -1):
	while pos >= 0 and a[pos] == '0':
		pos -= 1

	if (pos < 0):
		break

	if pos > 0:
		cur = int(a[0:pos]) + int(a[pos:len(a)])
		if ans == -1:
			ans = cur
		else:
			ans = min(ans, cur)

	pos -= 1

pos = n // 2

for it in range(n // 2, n // 2 + 5):
	while pos < n and a[pos] == '0':
		pos += 1

	if (pos >= n):
		break

	if pos > 0:
		cur = int(a[0:pos]) + int(a[pos:len(a)])
		if ans == -1:
			ans = cur
		else:
			ans = min(ans, cur)

	pos += 1

print(ans)

l = int(input())
n = input()
mid = l // 2

def f(pos):
    if pos == 0 or pos == l or n[pos] == '0':
        return False
    return True

arr = []

for i in range((l+1)//2):
    pos = mid - i
    if not (pos == 0 or pos == l or n[pos] == '0'):
        arr.append(pos)
    pos = mid + i
    if not (pos == 0 or pos == l or n[pos] == '0'):
        arr.append(pos)
    if len(arr) > 2:
        break

best_ans = int(n + '00')
for pos in arr:
    ans = int(n[:pos]) + int(n[pos:])
    best_ans = min(best_ans, ans)
print(best_ans)


n = int(input())
s = input()
al_l = []
al_r = []

for i in range(1, n):
	if(int(s[i]) > 0 and i <= n//2):
		al_l.append(i)
	
	if(int(s[i]) > 0 and i > n//2):
		al_r.append(i)
	if(len(al_r) == 3):
		break
	if(len(al_l) == 3):
		del al_l[0]


ans = int(s)
for x in al_l:
	ans = min(ans, int(s[0:x]) + int(s[x:]))

for x in al_r:
	ans = min(ans, int(s[0:x]) + int(s[x:]))

	
print(ans)

n=int(input())
s=input()
good=[]
for i in range(1,n):
  if(s[i] != '0'):
    good.append([max(n - i, i), i])
good = sorted(good)
if len(good) == 0:
  good.append([n - 1, n - 1])
ans = int(s[:good[0][1]:]) + int(s[-(n-good[0][1]):])
for i in range(0, min(len(good), 3)):
  ans = min(ans, int(s[:good[i][1]:]) + int(s[-(n-good[i][1]):]))
print(ans)

l = int(input())
n = input()

ind = []

for i in range(1, l):
    if n[i] == '0': continue
    ind.append((abs(i - (l / 2)), i))

ind.sort()
sol = -1

for i in range(min(4, len(ind))):
    (x, y) = ind[i]
    curr = int(n[:y]) + int(n[y:])
    if sol == -1 or curr < sol:
        sol = curr

print(sol)


n = int(input())
s = input()

len1 = n // 2
len2 = (n + 1) // 2
S = 10**100000

def calc (d):
    nonlocal S
    h = d
    while (h < n and s[h] == '0'):
        h += 1

    if (h < n):
        S = min(S, int(s[h:]) + int(s[:h]))

    h = d
    while (0 <= h and s[h] == '0'):
        h -= 1

    if (0 < h):
        S = min(S, int(s[h:]) + int(s[:h]))

calc(len1)
calc(len2)
print(S)


import sys
import math

N=int(input())
S=input().strip()
C=10**121212

mi=101010
for i in range(1,N):
	if S[i]!='0':
		mi=min(mi,max(i,N-i)+2)

for i in range(1,N):
	if S[i]!='0' and max(i,N-i)<=mi:
		T=int(S[0:i])+int(S[i:])
		C=min(C,T)

print(C)


n = int(input())
a = input()
l = (n - 1) // 2
r = n // 2;
while(a[l] == '0' and a[r] == '0') :
    l -= 1
    r += 1

# print(l)
# print(r)
ans = -1

if(a[l] != '0' and l > 0):
    x = int(a[0:l])
    y = int(a[l:len(a)])
    if(ans == -1 or ans > (x + y)) :
        ans = x + y

if(a[r] != '0'):
    x = int(a[0:r])
    y = int(a[r:len(a)])
    if(ans == -1 or ans > x + y) :
        ans = x + y
        
l -= 1
r += 1


if(l > 0 and a[l] != '0'):
    x = int(a[0:l])
    y = int(a[l:len(a)])
    if(ans == -1 or ans > (x + y)) :
        ans = x + y

if(r < len(a) and a[r] != '0'):
    x = int(a[0:r])
    y = int(a[r:len(a)])
    if(ans == -1 or ans > x + y) :
        ans = x + y

print(ans)

n=int(input())
s=input()
x=n//2
ans=int(s)
if(s[x]!='0'):
	ans=min(ans,int(s[:x])+int(s[x:]))
for i in range(x+1,n):
	if(s[i]!='0'):
		ans=min(ans,int(s[:i])+int(s[i:]))
		break
for i in range(x-1,0,-1):
	if(s[i]!='0'):
	#	print(i,s[:i],s[i:])
		ans=min(ans,int(s[:i])+int(s[i:]))
		break
print(ans)

import math
n = int(input())
k = input()

def st(s):
    if(s == ''):
        return 0
    return int(s)
def cal(pos):
    if(k[pos] == '0'):
        return 1 << 400000
    return st(k[:pos]) + st(k[pos:])


mid_L = (n + 1) // 2
mid_R = n // 2
sum = -1;
while(k[mid_L] == k[mid_R] == '0'):
    mid_L-=1
    mid_R+=1

sum = min(cal(mid_L), cal(mid_R))
print(sum)

T = int(input())
s = input()
mid = len(s) // 2
MIN = -1

if len(s) < 3:
	print(int(s[0]) + int(s[1]))
	return

for i in range(mid, -1, -1):
	if s[i+1] != '0':
		MIN = int(s[:i+1]) + int(s[i+1:])
		break

for i in range(mid, len(s)):
	if s[i] != '0':
		tmp = int(s[:i]) + int(s[i:])
		if MIN > tmp:
			MIN = tmp
		break

if MIN == -1:
	MIN = int(s[:len(s)-1]) + int(s[len(s)-1:])

print(MIN)

l = int(input())
s = input()

mi = int(s)

c=0
for i in range(int(l/2+1),l):
    if(s[i] == '0'):
        continue
    n1 = int(s[:i])
    n2 = int(s[i:])

    mi = min(mi, n1 + n2);
    c += 1
    if(c>=2):
        break

c=0
for i in range(int(l/2),0,-1):
    if(s[i] == '0'):
        continue
    n1 = int(s[:i])
    n2 = int(s[i:])

    mi = min(mi, n1 + n2);
    break
    c += 1
    if(c>=2):
        break

print(mi)


import math

n = int(input())
s = input()

mini = math.inf
digits = 10**5 + 10

for i in range(n//2, n):
    if s[i] != '0':
        a = i
        b = n - i
        if max(a, b) > digits + 2:
            continue
        else:
            mini = min(mini, int(s[:i]) + int(s[i:]))
            digits = math.log10(mini) + 1

for i in range(n//2 - 1, 0, -1):
    if s[i] != '0':
        a = i
        b = n - i
        if max(a, b) > digits + 2:
            continue
        else:
            mini = min(mini, int(s[:i]) + int(s[i:]))
            digits = math.log10(mini) + 1


print(mini)

l = int(input()) 
num = input()

smallest = 1000000
points = []
for i,c in enumerate(num):
    if i == 0: continue
    if (c != '0'):
        if max(i,l-i) < smallest:
            smallest = max(i,l-i)
            points.clear()
        if max(i,l-i) == smallest:
            points.append(i)


ans = int("9" * 100000)
for val in points:
    ans = min(ans,int(num[:val]) + int(num[val:]))

print(ans)