#include <iostream>
#include <vector>
#include <string>

struct Multiplicator {
    void simple_multiply(std::vector<int>& a, std::vector<int>& b, std::vector<int>& res) {
        res.resize(a.size() + b.size());
        for(std::size_t i = 0; i < b.size(); i++) {
            for(std::size_t j = 0; j < a.size(); j++) {
                res[i + j] += b[i] * a[j];
            }
        }
    }

    void sum(std::vector<int>& a, std::vector<int>& b, std::vector<int>& res) {
        res.resize(std::max(a.size(), b.size()));
        if(a.size() < b.size()) {
            std::swap(a, b);
        }
        res = a;
        for(std::size_t i = 0; i < b.size(); i++) {
            res[i] += b[i];
        }
    }

    void decrease(std::vector<int>& a, std::vector<int>& b, std::vector<int>& res) {
        res.resize(std::max(a.size(), b.size()));
        res = a;
        for(std::size_t i = 0; i < b.size(); i++) {
            res[i] -= b[i];
        }
    }

    void prepareNumbers(std::vector<int>& a, std::vector<int>& b, std::vector<int>& res) {
        if(a.size() < b.size()) {
            std::swap(a, b);
        }

        while(b.size() < a.size()) {
            b.push_back(0);
        }
        while((b.size() & 1)) {
            a.push_back(0);
            b.push_back(0);
        }
    }

    void split(std::vector<int>& al, std::vector<int>& ar,
                std::vector<int>& bl, std::vector<int>& br,
                std::vector<int>& a, std::vector<int>& b, int mid) {
        for(std::size_t i = 0; i < a.size(); i++) {
            if(i < mid) {
                al.push_back(a[i]);
                bl.push_back(b[i]);
            }
            else {
                ar.push_back(a[i]);
                br.push_back(b[i]);
            }
        }
    }

    void reverseParts(std::vector<int>& r1, std::vector<int>& r2, std::vector<int>& r4) {
        reverse(r1.begin(), r1.end());
        reverse(r2.begin(), r2.end());
        reverse(r4.begin(), r4.end());
    }

    void multiplyParts(std::vector<int>& r1, std::vector<int>& r2,
                        std::vector<int>& r4, std::vector<int>& al,
                        std::vector<int>& bl, std::vector<int>& kl,
                        std::vector<int>& kr, std::vector<int>& ar,
                        std::vector<int>& br) {
        multiply(al, bl, r1);
        multiply(kl, kr, r2);
        multiply(ar, br, r4);
    }

    void sumParts(std::vector<int>& al, std::vector<int>& bl,
                    std::vector<int>& kl, std::vector<int>& kr,
                    std::vector<int>& ar, std::vector<int>& br) {
        sum(al, ar, kl);
        sum(bl, br, kr);
    }

    void multiply(std::vector<int>& a, std::vector<int>& b, std::vector<int>& res) {
        if(std::max(a.size(), b.size()) < 100) {
            simple_multiply(a, b, res);
            return;
        }
        prepareNumbers(a, b, res);
        int mid = a.size() / 2;
        std::vector<int> al;
        std::vector<int> ar;
        std::vector<int> bl;
        std::vector<int> br;
        split(al, ar, bl, br, a, b, mid);
        std::vector<int> r1;
        std::vector<int> r2;
        std::vector<int> r3;
        std::vector<int> r4;
        std::vector<int> kl;
        std::vector<int> kr;
        sumParts(al, bl, kl, kr, ar, br);
        multiplyParts(r1, r2, r4, al, bl, kl, kr, ar, br);
        reverseParts(r1, r2, r4);
        decrease(r2, r1, r3);
        decrease(r3, r4, r2);
        for(std::size_t i = 0; i < mid; i++) {
            r2.push_back(0);
        }
        for(std::size_t i = 0; i < 2 * mid; i++) {
            r4.push_back(0);
        }
        reverseParts(r1, r2, r4);
        sum(r1, r2, res);
        std::vector<int> res2;
        sum(res, r4, res2);
        res = res2;
    }
};

class BigInteger {
    private:
        std::vector<int> base;
        bool negative = 0;
    public:

        BigInteger() = default;

        BigInteger(int a) {
            if(a < 0) {
                negative = 1;
            }
            a = abs(a);
            base.clear();
            while(a != 0) {
                base.push_back(a % 10);
                a /= 10;
            }
        }

        BigInteger& operator=(int a) {
            if(a < 0) {
                negative = 1;
            }
            a = abs(a);
            base.clear();
            while(a != 0) {
                base.push_back(a % 10);
                a /= 10;
            }
        }

        BigInteger& operator+= (const BigInteger& int2) {
            BigInteger nw = *this + int2;
            base = nw.base;
            negative = nw.negative;
            return *this;
        }

        BigInteger& operator-= (const BigInteger& int2) {
            BigInteger nw = *this - int2;
            base = nw.base;
            negative = nw.negative;
            return *this;
        }

        BigInteger& operator*= (const BigInteger& int2) {
            BigInteger nw = *this * int2;
            base = nw.base;
            negative = nw.negative;
            return *this;
        }

        BigInteger& operator/= (const BigInteger& int2) {
            BigInteger nw = *this / int2;
            base = nw.base;
            negative = nw.negative;
            return *this;
        }

        BigInteger& operator%= (const BigInteger& int2) {
            BigInteger nw = *this % int2;
            base = nw.base;
            negative = nw.negative;
            return *this;
        }

        BigInteger operator- () {
            negative = !negative;
            return *this;
        }

        bool isLess(const BigInteger& int2) {
            if(base.size() < int2.base.size()) {
                return true;
            }
            if(base.size() > int2.base.size()) {
                return false;
            }
            for(std::size_t i = base.size() - 1; i >= 0; i--) {
                if(base[i] < int2.base[i]) {
                    return true;
                }
                if(base[i] > int2.base[i]) {
                    return false;
                }
                if(i == 0) {
                    break;
                }
            }
            return false;
        }

        bool operator< (const BigInteger& int2) {
            BigInteger int2Copy = int2;
            if(*this == BigInteger(0)) {
                negative = false;
            }
            if(int2 == BigInteger(0)) {
                int2Copy.negative = false;
            }
            if(negative != int2Copy.negative) {
                return ((negative) ? true : false);
            }
            else {
                return (isLess(int2Copy) != negative);
            }
        }

        bool operator> (const BigInteger& int2) {
            return !(*this < int2) && *this != int2;
        }

        bool operator<= (const BigInteger& int2) {
            return !(*this > int2);
        }

        bool operator>= (const BigInteger& int2) {
            return !(*this < int2);
        }

        BigInteger& operator++() {
            *this = *this + BigInteger(1);
            if(*this >= BigInteger(0)) {
                negative = false;
            }
            return *this;
        }

        BigInteger operator++(int) {
            BigInteger current = *this;
            ++*this;
            if(*this >= BigInteger(0)) {
                negative = false;
            }
            return current;
        }

        operator bool() const {
            return !(BigInteger(*this) == BigInteger(0));
        }

        std::string toString() {
            std::string ans = "";
            for(int i : base) {
                ans += (i + '0');
            }
            reverse(ans.begin(), ans.end());
            return ans;
        }

        std::vector<int> getBase() const {
            return base;
        }

        bool getNegative() const {
            return negative;
        }

        void setNegative(bool value) {
            negative = value;
        }

        void setBase(std::vector<int> value) {
            base = value;
        }

        void pushBack(int value) {
            base.push_back(value);
        }

        void popBack() {
            base.pop_back();
        }

        void updateNext(int value) {
            base[value + 1] += base[value] / 10;
        }

        // Could be overflow
        int toInt() {
            int ans = 0;
            int pw = 1;
            for(std::size_t i = 0; i < base.size(); i++) {
                ans += base[i] * pw;
                pw *= 10;
            }
            return ans;
        }

        friend std::ostringstream& operator<<(std::ostringstream& os, const BigInteger& integer);
        friend std::ostream& operator<<(std::ostream& os, const BigInteger& integer);
        friend std::istringstream& operator>>(std::istringstream& is, BigInteger& integer);
        friend bool operator== (const BigInteger& int1, const BigInteger& int2);
        friend bool operator!= (const BigInteger& int1, const BigInteger& int2);
        friend BigInteger operator+ (const BigInteger& int1, const BigInteger& int2);
        friend BigInteger operator- (const BigInteger& int1, const BigInteger& int2);
        friend BigInteger operator* (const BigInteger& int1, const BigInteger& int2);
        friend BigInteger operator/ (const BigInteger& int1, const BigInteger& int2);
        friend BigInteger operator% (const BigInteger& int1, const BigInteger& int2);

};

bool checkDifferentSignsZeros(const std::vector<int>& base1, const std::vector<int>& base2) {
    return (base1.size() == 1 && base1[0] == 0 && base2[0] == 0);
}

bool operator== (const BigInteger& int1, const BigInteger& int2) {
    std::vector<int> base1 = int1.getBase();
    std::vector<int> base2 = int2.getBase();
    if(base1.size() != base2.size()) {
        return false;
    }
    if(checkDifferentSignsZeros(base1, base2)) {
        return true;
    }
    if(int1.getNegative() != int2.getNegative()) {
        return false;
    }
    for(std::size_t i = 0; i < base1.size(); i++) {
        if(base1[i] != base2[i]) {
            return false;
        }
    }
    return true;
}

bool operator!= (const BigInteger& int1, const BigInteger& int2) {
    return !(int1 == int2);
}

std::ostringstream& operator<<(std::ostringstream& os, const BigInteger& integer) {
    os << ((integer.getNegative()) ? "-" : "");
    std::vector<int> base = integer.getBase();
    for(std::size_t i = base.size() - 1; i >= 0; i--) {
        os << base[i];
        if(i == 0) {
            break;
        }
    }
    return os;
}

std::ostream& operator<<(std::ostream& os, const BigInteger& integer) {
    os << ((integer.getNegative()) ? "-" : "");
    std::vector<int> base = integer.getBase();
    for(std::size_t i = base.size() - 1; i >= 0; i--) {
        os << base[i];
        if(i == 0) {
            break;
        }
    }
    return os;
}

std::istringstream& operator>>(std::istringstream& is, BigInteger& integer) {
    integer.base.clear();
    std::string s;
    is >> s;
    for(int i = s.size() - 1; i >= 0; i--) {
        integer.base.push_back(s[i] - '0');
    }
    return is;
}

BigInteger operator+ (const BigInteger& int1, const BigInteger& int2) {
    int next = 0;
    BigInteger answer;
    BigInteger a = int1;
    BigInteger b = int2;
    std::vector<int> aBase = a.getBase();
    std::vector<int> bBase = b.getBase();
    if(a.getNegative() == false && b.getNegative() == false) {
        answer.setNegative(false);
    }
    else if(a.getNegative()  && !b.getNegative()) {
        a.setNegative(false);
        answer = b - a;
        return answer;
    }
    else if(!a.getNegative() && b.getNegative()) {
        b.setNegative(false);
        answer = a - b;
        return answer;
    }
    else {
        answer.setNegative(true);
    }
    if(a < b) {
        std::swap(a, b);
    }

    for(std::size_t i = 0; i < aBase.size(); i++) {
        if(i < bBase.size()) {
            int num = aBase[i] + bBase[i] + next;
            answer.pushBack(num % 10);
            next = (num / 10) % 10;
        }
        else {
            answer.pushBack(aBase[i] + next);
            next = 0;
        }
    }
    if(next != 0) {
        answer.pushBack(next);
    }
    return answer;
}



BigInteger operator- (const BigInteger& int1, const BigInteger& int2) {
    BigInteger answer;
    BigInteger a = int1;
    BigInteger b = int2;
    std::vector<int> aBase = a.getBase();
    std::vector<int> bBase = b.getBase();
    if(a.getNegative() == false && b.getNegative() == false) {
        answer.setNegative(false);
    }
    else if(a.getNegative() && !b.getNegative()) {
        a.setNegative(false);
        answer = a + b;
        answer.setNegative(true);
        return answer;
    }
    else if(!a.getNegative() && b.getNegative()) {
        b.setNegative(false);
        answer = a + b;
        answer.setNegative(false);
        return answer;
    }
    else {
        std::swap(a, b);
        answer.setNegative(false);
    }
    int inverse = 0;
    if(a < b) {
        std::swap(a, b);
        inverse = 1;
    }
    int add = 0;
    for(std::size_t i = 0; i < aBase.size(); i++) {
        if(i < bBase.size()) {
            if(aBase[i] - add >= bBase[i]) {
                answer.pushBack(aBase[i] - add - bBase[i]);
            }
            else {
                answer.pushBack(aBase[i] - add - bBase[i] + 10);
                add = 1;
            }
        }
        else {
            if(aBase[i] >= add) {
                answer.pushBack(aBase[i] - add);
                add = 0;
            }
            else {
                answer.pushBack(10 - add);
                add = 1;
            }
        }
    }
    while(answer.getBase().size() && answer.getBase().back() == 0) {
        answer.popBack();
    }
    if(answer.getBase().size() == 0) {
        answer.pushBack(0);
    }
    answer.setNegative(!inverse);
    return answer;
}

BigInteger operator* (const BigInteger& int1, const BigInteger& int2) {
    BigInteger a = int1;
    BigInteger b = int2;
    BigInteger answer;
    Multiplicator multiplicator;
    std::vector<int> aBase = a.getBase();
    std::vector<int> bBase = b.getBase();
    std::vector<int> answerBase = answer.getBase();
    multiplicator.multiply(aBase, bBase, answerBase);
    answer.setBase(answerBase);
    if(a.getNegative() ^ b.getNegative()) {
        answer.setNegative(true);
    }
    else {
        answer.setNegative(false);
    }
    for(std::size_t i = 0; i < answer.getBase().size() - 1; i++) {
        if(i < answer.getBase().size() - 1) {
            answer.updateNext(i);
            answer.base[i] %= 10;
        }
    }
    while(answer.getBase().back() != 0) {
        int cnt = answer.getBase().back();
        answer.base[answer.base.size() - 1] %= 10;
        answer.pushBack(cnt / 10);

    }
    while(answer.getBase().size() && answer.getBase().back() == 0) {
        answer.base.pop_back();
    }
    if(answer.getBase().size() == 0) {
        answer.pushBack(0);
    }
    return answer;
}

BigInteger operator/ (const BigInteger& int1, const BigInteger& int2) {
    BigInteger a = int1;
    BigInteger b = int2;
    BigInteger answer;
    std::vector<int> aBase = a.getBase();
    std::vector<int> bBase = b.getBase();
    if(a.getNegative() ^ b.getNegative()) {
        answer.setNegative(true);
    }
    else {
        answer.setNegative(false);
    }
    a.setNegative(false);
    b.setNegative(false);
    int pos = aBase.size() - 1;
    BigInteger cur = 0;
    while(pos >= 0) {
        cur = cur * BigInteger(10) + BigInteger(aBase[pos]);
        pos--;
        if(cur >= b) {
            int num;
            for(int i = 0; i < 10; i++) {
                if(b * BigInteger(i) > cur) {
                    num = i - 1;
                    break;
                }
            }
            BigInteger bigNum = num;
            cur = cur - (b * bigNum);
            answer.pushBack(num);
        }
        else {
            answer.pushBack(0);
        }
    }
    reverse(answer.getBase().begin(), answer.getBase().end());
    while(answer.getBase().size() && answer.getBase().back() == 0) {
        answer.popBack();
    }
    if(answer.getBase().size() == 0) {
        answer.pushBack(0);
    }
    return answer;
}

BigInteger operator% (const BigInteger& int1, const BigInteger& int2) {
    BigInteger a = int1;
    BigInteger b = int2;
    BigInteger answer = a;
    std::vector<int> aBase = a.getBase();
    std::vector<int> bBase = b.getBase();
    bool negative = a.getNegative();
    b.setNegative(false);
    int pos = aBase.size() - 1;
    BigInteger cur = 0;
    while(pos >= 0) {
        cur = cur * BigInteger(10) + BigInteger(aBase[pos]);
        pos--;
        if(cur >= b) {
            int num;
            for(int i = 0; i < 10; i++) {
                if(b * BigInteger(i) > cur) {
                    num = i - 1;
                    break;
                }
            }
            BigInteger bigNum = num;
            cur = cur - (b * bigNum);
            answer = cur;
        }
    }
    answer.setNegative(negative);
    return answer;
}