Big Integer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BigInt {
    static const int BASE = 1000000000;
    vector<int> v;

    BigInt() {}
    BigInt(ll val) { *this = val; }
    BigInt(const string &s) { *this = s; }

    int size() const { return (int)v.size(); }
    bool zero() const { return v.empty(); }

    ll val() const {
        ll ans = 0;
        for (int i = (int)v.size() - 1; i >= 0; i--)
            ans = ans * BASE + v[i];
        return ans;
    }

    void strip() { while (!v.empty() && v.back() == 0) v.pop_back(); }

    BigInt &operator=(ll val) {
        v.clear();
        for (; val > 0; val /= BASE) v.push_back(val % BASE);
        return *this;
    }

    BigInt &operator=(const string &s) {
        v.clear();
        for (int i = (int)s.size() - 1; i >= 0; i -= 9) {
            int st = max(0, i - 8);
            v.push_back(stoi(s.substr(st, i - st + 1)));
        }
        strip();
        return *this;
    }

    bool operator<(const BigInt &a) const {
        if (size() != a.size()) return size() < a.size();
        for (int i = size() - 1; i >= 0; i--)
            if (v[i] != a.v[i]) return v[i] < a.v[i];
        return false;
    }
    bool operator>(const BigInt &a) const { return a < *this; }
    bool operator==(const BigInt &a) const { return v == a.v; }
    bool operator<=(const BigInt &a) const { return !(a < *this); }
    bool operator>=(const BigInt &a) const { return !(*this < a); }

    BigInt operator+(const BigInt &a) const {
        BigInt res = *this;
        int carry = 0;
        for (int i = 0; i < (int)a.v.size() || carry; i++) {
            if (i == (int)res.v.size()) res.v.push_back(0);
            ll cur = res.v[i] + carry + (i < (int)a.v.size() ? a.v[i] : 0);
            res.v[i] = cur % BASE;
            carry = cur / BASE;
        }
        return res;
    }
    BigInt &operator+=(const BigInt &a) { return *this = *this + a; }

    BigInt operator-(const BigInt &b) const {
        BigInt res = *this;
        int borrow = 0;
        for (int i = 0; i < (int)b.v.size() || borrow; i++) {
            ll cur = res.v[i] - borrow - (i < (int)b.v.size() ? b.v[i] : 0);
            if (cur < 0) { cur += BASE; borrow = 1; }
            else borrow = 0;
            res.v[i] = cur;
        }
        res.strip();
        return res;
    }
    BigInt &operator-=(const BigInt &b) { return *this = *this - b; }

    BigInt operator*(const BigInt &a) const {
        if (zero() || a.zero()) return BigInt(0);
        BigInt res;
        res.v.resize(size() + a.size(), 0);
        for (int i = 0; i < size(); i++) {
            if (!v[i]) continue;
            ll carry = 0;
            for (int j = 0; j < (int)a.v.size() || carry; j++) {
                ll cur = res.v[i + j] + carry + 1LL * v[i] * (j < (int)a.v.size() ? a.v[j] : 0);
                res.v[i + j] = cur % BASE;
                carry = cur / BASE;
            }
        }
        res.strip();
        return res;
    }
    BigInt &operator*=(const BigInt &a) { return *this = *this * a; }

    BigInt &operator/=(ll a) {
        ll carry = 0;
        for (int i = (int)v.size() - 1; i >= 0; i--) {
            ll cur = v[i] + carry * BASE;
            v[i] = cur / a;
            carry = cur % a;
        }
        strip();
        return *this;
    }
    BigInt operator/(ll a) const { BigInt res = *this; res /= a; return res; }

    BigInt operator%(ll a) const {
        ll res = 0;
        for (int i = (int)v.size() - 1; i >= 0; i--)
            res = (res * BASE + v[i]) % a;
        return BigInt(res);
    }
    BigInt &operator%=(ll a) { return *this = *this % a; }

    friend ostream &operator<<(ostream &out, const BigInt &a) {
        if (a.zero()) return out << 0;
        out << a.v.back();
        for (int i = (int)a.v.size() - 2; i >= 0; i--)
            out << setfill('0') << setw(9) << a.v[i];
        return out;
    }

    friend istream &operator>>(istream &in, BigInt &a) {
        string s; in >> s; a = s; return in;
    }
};