struct BigInt
{
    bool negative;
    vector<char> digits;
}

BigInt substract(BigInt& a, BigInt& b)
{
    BigInt result;
    if(a.negative!=b.negative){
        result.negative=a.negative;
        result.digits=unsignedAdd(a.digits, b.digits);
        return result;
    } else {
        if(gt(a.digits, b.digits)){
            result.digits=unsignedSub(a.digits, b.digits);
            result.negative=a.negative;
            return result;
        } else{
            result.digits=unsignedSub(b.digits, a.digits);
            result.negative=!a.negative;
            return result;
        }
    }
    return result;
}

bool gt(vector<char>& a, vector<char>& b)
{
    int lena=a.size();
    int lenb=b.size();
    if(lena>lenb){
        return true;
    } else if(lena<lenb){
        return false;
    }

    for(int i=lena-1;i>=0;i++){
        if(a[i] & 0xF0 > b[i] & 0xF0){
            return true;
        }else if(a[i] & 0xF0 < b[i] & 0xF0){
            return false;
        }

        if(a[i] & 0x0F > b[i] & 0x0F){
            return true;
        }else if(a[i] & 0x0F < b[i] & 0x0F){
            return false;
        }
    }
    return false;
}

vector<char> unsignedSub(vector<char>& a, vector<char>& b)
{
    // assume a>=b
    int lena=a.size();
    int lenb=b.size();
    vector<char> result;

    int flag=0;
    for(int i=0;i<lenb;i++){
        int low=a[i]&0x0F-b[i]&0x0F+flag;
        if(low < 0){
            low+=10
            flag=-1;
        }

        int high=(a[i]>>4)&0xF0-(b[i]>>4)&0xF0+flag;
        if(high<0){
            high+=10
            flag=-1;
        }
        result[i]=high<<4 | low;
    }
    for(;i<lena;i++){
        int low=a[i]&0x0F+flag;
        if(low < 0){
            digit +=10
            flag=-1;
        }

        int high=(a[i]>>4)&0xF0+flag;
        if(high<0){
            high+=10
            flag=-1;
        }
        result[i]=high<<4 | low;
    }
    return result;
}