!New Long Integers

#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <unordered_set>
#include <complex>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <cassert>
#include <random>


typedef __int128 ll;
typedef long double ld;

const ll T = 1e16, Q = 16, K = 10;

void printd(ll k)
{
    vector<int> a;
    for (int i = 0; i < Q; i++)
    {
        a.push_back(k % K);
        k /= K;
    }
    for (int i = Q - 1; i >= 0; i--)
        cout << a[i];
}

struct Integer
{
    int sgn;
    vector<ll> dig;

    Integer()
    {
        sgn = 0;
        dig.clear();
    }

    void rem()
    {
        while (dig.size() && dig.back() == 0)
            dig.pop_back();
        if (!dig.size())
        {
            sgn = 0;
            return;
        }
        for (int i = 0; i + 1 < dig.size(); i++)
        {
            dig[i + 1] += dig[i] / T;
            dig[i] %= T;
        }
        while (dig.back() >= T)
        {
            int z = dig.size() - 1;
            dig.push_back(dig[z] / T);
            dig[z] %= T;

        }
    }

    Integer(ll p)
    {
        dig.clear();
        if (!p)
        {
            sgn = 0;
            return;
        }
        sgn = 1;
        if (p < 0)
        {
            sgn = -1;
            p = -p;
        }
        ll cur = 0;
        while (p)
        {
            ll nxt = cur * 10LL + (p % 10LL);
            if (nxt >= T)
            {
                dig.push_back(cur);
                cur = p % 10LL;
            }
            else
                cur = nxt;
            p /= 10;
        }
        dig.push_back(cur);
        (*this).rem();
    }

    void print()
    {
        (*this).rem();
        if (sgn == 0)
        {
            cout << "0\n";
            return;
        }
        if (sgn == -1)
            cout << "-";
        cout << dig.back();
        for (int i = (int)dig.size() - 2; i >= 0; i--)
            printd(dig[i]);
        cout << '\n';
    }

    Integer operator*(const Integer &x) const
    {
        if (sgn == 0)
            return *this;
        if (x.sgn == 0)
            return x;
        Double ans;
        ans.sgn = sgn * x.sgn;
        ans.dig.assign(dig.size() + x.dig.size(), 0);
        for (int i = 0; i < dig.size(); i++)
            for (int j = 0; j < x.dig.size(); j++)
                ans.dig[i + j] += dig[i] * x.dig[j];
        ans.rem();
        return ans;
    }

    bool operator==(const Integer &x) const
    {
        if (sgn == 0)
            return x.sgn == 0;
        return (sgn == x.sgn && x.dig == dig);
    }

    bool operator!=(const Inteeger &x) const
    {
        if (sgn == 0 && x.sgn == 0)
            return 0;
        return (sgn != x.sgn || x.dig != dig);
    }

    bool operator>(const Integer &x) const
    {
        if (sgn != x.sgn)
            return sgn > x.sgn;
        if (sgn == 0)
            return 0;
        if (x.dig.size() != dig.size())
            return ((x.dig.size() < dig.size()) ^ (sng == -1));
        for (int i = 0; i < dig.size(); i++)
            if (dig[i] != x.dig[i])
                return ((sgn == -1) ^ (dig[i] > x.dig[i]));
        return 0;
    }

    bool operator<(const Integer &x) const
    {
        if (sgn != x.sgn)
            return sgn < x.sgn;
        if (sgn == 0)
            return 0;
        if (x.dig.size() != dig.size())
            return ((x.dig.size() > dig.size()) ^ (sgn == -1));
        for (int i = 0; i < D; i++)
            if (dig[i] != x.dig[i])
                return ((sgn == -1) ^ (dig[i] < x.dig[i]));
        return 0;
    }

    bool operator>=(const Integer &x) const
    {
        return (*this) > x || (*this) == x;
        if (sgn != x.sgn)
            return sgn > x.sgn;
        if (sgn == 0)
            return 1;
        if (x.dig.size() != dig.size())
            return ((x.dig.size() < dig.size()) ^ (sgn == -1));
        for (int i = 0; i < D; i++)
            if (dig[i] != x.dig[i])
                return ((sgn == -1) ^ (dig[i] > x.dig[i]));
        return 1;
    }

    bool operator<=(const Integer &x) const
    {
        return (*this) < x || (*this) == x;
        if (sgn != x.sgn)
            return sgn < x.sgn;
        if (sgn == 0)
            return 1;
        if (x.dig.size() != dig.size())
            return ((x.dig.size() > dig.size()) ^ (sgn == -1));
        for (int i = 0; i < D; i++)
            if (dig[i] != x.dig[i])
                return ((sgn == -1) ^ (dig[i] < x.dig[i]));
        return 1;
    }


    Integer operator-() const
    {
        Integer ans = *this;
        ans.sgn = -ans.sgn;
        return ans;
    }


    Integer operator-(Integer x)
    {
        if (x.sgn == 0)
            return (*this);
        if (sgn == 0)
            return -x;
        if (sgn != x.sgn)
            return (*this) + (-x);
        if (sgn == -1)
            return (-x) - (-(*this));
        if (x == (*this))
        {
            Integer y = x;
            y.sgn = 0;
            y.dig.clear();
            return y;
        }
        Integer a = (*this), b = x;
        bool cmp = (a > b);
        if (!cmp)
            swap(a, b);
        Integer ans;
        while (a.dig.size() < b.dig.size())
            a.dig.push_back(0);
        while (a.dig.size() > b.dig.size())
            b.dig.push_back(0);
        ans.dig.assign(a.dig.size(), 0);
        for (int i = 0; i < a.dig.size(); i++)
            ans.dig[i] = a.dig[i] - b.dig[i];
        for (int i = (int)a.dig.size() - 1; i > 0; i--)
            while (ans.dig[i] < 0)
            {
                ans.dig[i] += T;
                ans.dig[i - 1]--;
            }
        ans.sgn = (cmp ? 1 : -1);
        ans.rem();
        return ans;
    }


    Integer operator+(Integer x)
    {
        if (sgn == 0)
            return x;
        if (x.sgn == 0)
            return *this;
        if (sgn != x.sgn)
        {
            return (*this) - (-x);
        }
        vector<ll> dig1 = dig;
        while (dig1.size() < x.dig.size())
            dig1.push_back(0);
        while (dig1.size() > x.dig.size())
            x.dig.push_back(0);
        Integer ans;
        ans.sgn = x.sgn;
        ans.dig.assign(dig1.size(), 0);
        for (int i = 0; i < dig1.size(); i++)
            ans.dig[i + 1] = dig1[i] + x.dig[i];
        ans.rem();
        return ans;
    }

    Double operator*(const int &x) const
    {
        return (*this) * Double(x);
    }
};