#include<cstdio>
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

struct Big_Int
{
    static const int BASE=1e4,WIDTH=4;

    vector<int> s;

    inline Big_Int operator=(const string &str)
    {
        s.clear();
        int x,len=(str.size()-1)/WIDTH+1;
        for(register int i=0;i<len;i++)
        {
            int end=str.size()-i*WIDTH,start=max(0,end-WIDTH);
            sscanf(str.substr(start,end-start).c_str(),"%d",&x);
            s.push_back(x);
        }
        return *this;
    }

    inline friend bool operator<(const Big_Int &a,const Big_Int &b)
    {
        if(a.s.size()!=b.s.size()) return a.s.size()<b.s.size();
        for(register int i=a.s.size()-1;~i;i--)
            if(a.s[i]!=b.s[i]) return a.s[i]<b.s[i];
        return 0;
    }

    inline friend Big_Int operator+(const Big_Int &a,const Big_Int &b)
    {
        Big_Int c;
        for(register int i=0,t=0;;i++)
        {
            if(t==0&&i>=a.s.size()&&i>=b.s.size()) break;
            int x=t;
            if(i<a.s.size()) x+=a.s[i];
            if(i<b.s.size()) x+=b.s[i];
            c.s.push_back(x%BASE);
            t=x/BASE;
        }
        return c;
    }

    inline friend Big_Int operator-(const Big_Int &a,const Big_Int &b)
    {
        Big_Int c;
        for(register int i=0,t=0;i<a.s.size();i++)
        {
            t=a.s[i]-t;
            if(i<b.s.size()) t-=b.s[i];
            c.s.push_back((t+BASE)%BASE);
            if(t<0) t=1;
            else t=0;
        }
        while(c.s.size()>1&&c.s.back()==0) c.s.pop_back();
        return c;
    }

    inline friend Big_Int operator*(const Big_Int &a,const int b)
    {
        Big_Int c;
        for(register int i=0,t=0;i<a.s.size()||t;i++)
        {
            if(i<a.s.size()) t+=a.s[i]*b;
            c.s.push_back(t%BASE);
            t/=BASE;
        }
        while(c.s.size()>1&&c.s.back()==0) c.s.pop_back();
        return c;
    }

    inline friend Big_Int div(const Big_Int &a,const int b,int &r)
    {
        Big_Int c;
        r=0;
        for(register int i=a.s.size()-1;~i;i--)
        {
            r=r*BASE+a.s[i];
            c.s.push_back(r/b);
            r%=b;
        }
        reverse(c.s.begin(),c.s.end());
        while(c.s.size()>1&&c.s.back()==0) c.s.pop_back();
        return c;
    }

    inline void print() const
    {
        printf("%d",s.back());
        for(register int i=s.size()-2;~i;i--) printf("%04d",s[i]);
        puts("");
    }
};

int main(void)
{

    return 0;
}