struct bigint {
    static const int base = 100000000;
    static const int base_digits = 8;

    int z[30];
    int zs;

    bigint(): zs(0) {}

    bigint(long long v) {
        *this = v;
    }

    bigint& operator=(long long v) {
        zs = 0;
        for (; v > 0; v = v / base)
            push_back(v % base);
        return *this;
    }

    bigint operator+(const bigint &v) const {
        bigint res = v;

        for (int i = 0, carry = 0; i < (int) max(zs, v.zs) || carry; ++i) {
            if (i == (int) res.zs)
                res.push_back(0);
            res.z[i] += carry + (i < (int) zs ? z[i] : 0);
            carry = res.z[i] >= base;
            if (carry)
                res.z[i] -= base;
        }
        return res;
    }

    bigint operator-(const bigint &v) const {
        bigint res = *this;
        for (int i = 0, carry = 0; i < (int) v.zs || carry; ++i) {
            res.z[i] -= carry + (i < (int) v.zs ? v.z[i] : 0);
            carry = res.z[i] < 0;
            if (carry)
                res.z[i] += base;
        }
        res.trim();
        return res;
    }

    bigint& operator+=(const bigint &v) {
        return *this = *this + v;
    }

    void trim() {
        while (zs != 0 && z[zs-1] == 0)
            zs--;
    }

    bigint operator*(const bigint &v) const {
        static long long vres[30];
        memset(vres, 0, sizeof(vres[0]) * (zs + v.zs));
        for (int i = 0; i < zs; i++) {
            for (int j = 0; j < v.zs; j++) {
                vres[i + j] += (long long)z[i] * (long long)v.z[j];
            }
        }

        bigint res;
        for (int i = 0, carry = 0; i < zs + v.zs; i++) {
            long long cur = vres[i] + carry;
            res.push_back((int) (cur % base));
            carry = (int) (cur / base);
        }
        res.trim();
        return res;
    }

    void push_back(long long i) {
        z[zs++] = i;
    }

    friend ostream& operator<<(ostream &stream, const bigint &v) {
        stream << (v.zs == 0 ? 0 : v.z[v.zs - 1]);
        for (int i = (int) v.zs - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.z[i];
        return stream;
    }
};