B. Split a Number（字符串加法）-蒲公英云

B. Split a Number（字符串加法）

Dima worked all day and wrote down on a long paper strip his favorite number nn consisting of ll 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 ll (2≤l≤1000002≤l≤100000) — the length of the Dima’s favorite number.

The second line contains the positive integer nn initially written on the strip: the Dima’s favorite number.

The integer nn consists of exactly ll 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

Copy

7
1234567

output

Copy

input

Copy

3
101

output

Copy

Note

In the first example Dima can split the number 12345671234567 into integers 12341234 and 567567. Their sum is 18011801.

In the second example Dima can split the number 101101 into integers 1010 and 11. Their sum is 1111. Note that it is impossible to split the strip into “1” and “01” since the numbers can’t start with zeros.

题解：从中间往两边分出两个分支，取最优解即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string cal(string a,string b)//字符串加法，模拟数的加法即可
{
    string ans="";
    int pos1=a.size()-1,pos2=b.size()-1;
    int last=0,x=0;
    while(1){
        if(pos1<0&&pos2<0)break;
        if(pos1<0&&pos2>=0){
            while(pos2>=0){
                x=b[pos2--]-'0'+last;
                if(x>=10){
                    last=x/10;
                    x%=10;
                }
                else
                    last=0;
                ans+=x+'0';
            }
            break;
        }
        if(pos2<0&&pos1>=0){
            while(pos1>=0){
                x=a[pos1--]-'0'+last;
                if(x>=10){
                    last=x/10;
                    x%=10;
                }
                else
                    last=0;
                ans+=x+'0';
            }
            break;
        }
        x=a[pos1--]-'0'+b[pos2--]-'0'+last;
        if(x>=10){
            last=x/10;
            x%=10;
        }
        else
            last=0;
        ans+=x+'0';
    }
    if(last)
        ans+=last+'0';
    return ans;
}
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int pos1=n/2,pos2=n/2+1;
    while(s[pos1]=='0'&&pos1>0)pos1--;
    while(s[pos2]=='0'&&pos2<n-1)pos2++;
    string a=s.substr(0,pos1);
    string b=s.substr(pos1,s.size());
    string ans=cal(a,b);
    reverse(ans.begin(),ans.end());
    string aa=s.substr(0,pos2);
    string bb=s.substr(pos2,s.size());
    string anss=cal(aa,bb);
    reverse(anss.begin(),anss.end());
    if(s[pos2]=='0')//特判后一部分不能分的情况，如果想到的话，这个题比赛的时候就能做出来了丫丫丫
        return cout<<ans<<endl,0;
    if(ans.size()<anss.size())cout<<ans<<endl;
    else if(ans.size()>anss.size())cout<<anss<<endl;
    else{
        if(ans<anss)
            cout<<ans<<endl;
        else
            cout<<anss<<endl;
    }
    return 0;
}