Bignum

/// M là số chữ số ước lượng, nhớ thay đổi với các bài/ Bản dùng vector ở đây: https://pastebin.com/tvmKwAQA
/// Nếu không có phép nhân thì nên đẩy BASE lên 1e17 hoặc 1e18
/// a = Bignum(5) || a = Bignum("5") đều được, tuy nhiên khuyến khích dùng loại 1
/// cin >> a hay a.read() đều được
/// cout << a hay a.print() đều được, khuyến khích dùng loại 1
/// Phép chia và phép mod chỉ dùng cho số nguyên và cho ra kết quả nguyên
/// Phép nhân fft

using cd = complex<long double>;
const long double PI = acos(-1);
const int M = 64;
const ll BASE = 1e7;
const int gd = log10(BASE);
const int maxn = M / gd + 1;
struct Bignum
{
    int n;
    ll a[maxn];
    Bignum(ll x = 0)
    {
        memset(a, 0, sizeof a);
        n = 0;
        do
        {
            a[n++] = x % BASE;
            x /= BASE;
        } while (x);
    }
    Bignum(const string &s)
    {
        Convert(s);
    }
    ll stoll(const string &s)
    {
        ll ans(0);
        for (auto i : s)
            ans = ans * 10 + i - '0';
        return ans;
    }
    void Convert(const string &s)
    {
        memset(a, 0, sizeof a);
        n = 0;
        for (int i = s.size() - 1; ~i; --i)
        {
            int j = max(0, i - gd + 1);
            a[n++] = stoll(s.substr(j, i - j + 1));
            i = j;
        }
        fix();
    }
    void fix()
    {
        ++n;
        for (int i = 0; i < n - 1; ++i)
        {
            a[i + 1] += a[i] / BASE;
            a[i] %= BASE;
            if (a[i] < 0)
            {
                a[i] += BASE;
                --a[i + 1];
            }
        }
        while (n > 1 && a[n - 1] == 0)
            --n;
    }
    Bignum &operator+=(const Bignum &x)
    {
        n = max(n, x.n);
        for (int i = 0; i < n; ++i)
            a[i] += x.a[i];
        fix();
        return *this;
    }
    Bignum &operator-=(const Bignum &x)
    {
        for (int i = 0; i < x.n; ++i)
            a[i] -= x.a[i];
        fix();
        return *this;
    }
    void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
    }
    Bignum &operator*=(const Bignum &x)
    {
        int m = 1;
        while (m < n + x.n)
            m <<= 1;
        vector<cd> fa(m), fb(m);
        for (int i = 0; i < m; ++i)
        {
            fa[i] = a[i];
            fb[i] = x.a[i];
        }
        fft(fa, false); /// dft
        fft(fb, false); /// dft
        for (int i = 0; i < m; i++)
            fa[i] *= fb[i];
        fft(fa, true); ///Interpolation
        n = m;
        for (int i = 0; i < n; ++i)
            a[i] = round(fa[i].real());
        fix();
        return *this;
    }
    Bignum &operator/=(const ll &x)
    {
        ll r = 0ll;
        for (int i = n - 1; i > -1; --i)
        {
            r = r * BASE + a[i];
            a[i] = r / x;
            r %= x;
        }
        fix();
        return *this;
    }
    Bignum operator+(const Bignum &s)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c += s;
        return c;
    }
    Bignum operator-(const Bignum &s)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c -= s;
        return c;
    }
    Bignum operator*(const Bignum &s)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c *= s;
        return c;
    }
    Bignum operator/(const ll &x)
    {
        Bignum c;
        copy(a, a + n, c.a);
        c.n = n;
        c /= x;
        return c;
    }
    ll operator%(const ll &x)
    {
        ll ans(0);
        for (int i = n - 1; ~i; --i)
            ans = (ans * BASE + a[i]) % x;
        return ans;
    }
    int com(const Bignum &s) const
    {
        if (n < s.n)
            return 1;
        if (n > s.n)
            return 2;
        for (int i = n - 1; i > -1; --i)
            if (a[i] > s.a[i])
                return 2;
            else if (a[i] < s.a[i])
                return 1;
        return 3;
    }
    bool operator<(const Bignum &s) const
    {
        return com(s) == 1;
    }
    bool operator>(const Bignum &s) const
    {
        return com(s) == 2;
    }
    bool operator==(const Bignum &s) const
    {
        return com(s) == 3;
    }
    bool operator<=(const Bignum &s) const
    {
        return com(s) != 2;
    }
    bool operator>=(const Bignum &s) const
    {
        return com(s) != 1;
    }
    void read()
    {
        string s;
        cin >> s;
        Convert(s);
    }
    void print()
    {
        int i = n;
        while (i > 0 && a[i] == 0)
            --i;
        cout << a[i];
        for (--i; ~i; --i)
            cout << setw(gd) << setfill('0') << a[i];
    }
    friend istream &operator>>(istream &in, Bignum &x)
    {
        string s;
        in >> s;
        x.Convert(s);
        return in;
    }
    friend ostream &operator<<(ostream &out, const Bignum &x)
    {
        int i = x.n;
        while (i > 0 && x.a[i] == 0)
            --i;
        out << x.a[i];
        for (--i; ~i; --i)
            out << setw(gd) << setfill('0') << x.a[i];
        return out;
    }
};