!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>

#define sz(a) (int)((a).size())

using namespace std;

mt19937 rnd(239);

typedef __int128 ll;
typedef long double ld;

const ll B = 1e16, Q = 16, T = 10;//B - BASE; T^Q = B

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

//+=, -=, *= ... need to be upgraded because now they just use operation
// |, |= - not implemented fft multiplication
// operations with short numbers are now implemented using transforming short numbers into big
// Sqrt and dividing(/) and mod(%) by BigInt is implimented with binary search. I don't think that it's the best option

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

    void rem()
    {
        while (dig.size() && dig.back() == 0)
            dig.pop_back();
        if (!dig.size())
            sgn = 0;
    }


    BigInt(ll x = 0)
    {
        if (!x)
            sgn = 0;
        else if (x < 0)
        {
            x = -x;
            sgn = -1;
        }
        else
            sgn = 1;
        while (x)
        {
            dig.push_back(x % B);
            x /= B;
        }
    }

    int size()
    {
        return dig.size();
    }

    int back()
    {
        if (!dig.size())
            return 0;
        return dig.back();
    }

    void rev()
    {
        reverse(dig.begin(), dig.end());
    }

    void push_back(ll x)
    {
        dig.push_back(x);
    }

    void read()
    {
        dig.clear();
        string s;
        cin >> s;
        bool ok = 0;
        for (int i = 0; i < size(); i++)
            if (s[i] != '0' && s[i] != '-')
            {
                ok = 1;
                break;
            }
        if (!ok)
        {
            sgn = 0;
            return;
        }
        int l;
        if (s[0] == '-')
        {
            sgn = -1;
            l = 1;
        }
        else
        {
            sgn = 1;
            l = 0;
        }
        for (int i = (int)s.size() - 1; i >= l; i -= Q)
        {
            ll cur = 0;
            for (int j = max(l, i - (int)Q + 1); j <= i; j++)
                cur = T * cur + (ll)(s[j] - '0');
            dig.push_back(cur);
        }
        (*this).rem();
    }

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

    ll operator[](const int k) const
    {
        if (k < 0)
        {
            cerr << "BigInt: taking digit with negative index" << endl;
            exit(0);
        }
        if (k >= dig.size())
            return 0;
        return dig[k];
    }

    bool operator<(BigInt x)
    {
        (*this).rem();
        x.rem();
        if (sgn != x.sgn)
            return sgn < x.sgn;
        if (x.size() != dig.size())
            return dig.size() < x.size();
        for (int i = x.size() - 1; i >= 0; i--)
            if (x[i] != dig[i])
                return dig[i] < x[i];
        return 0;
    }

    bool operator>(BigInt x)
    {
        (*this).rem();
        x.rem();
        if (sgn != x.sgn)
            return sgn > x.sgn;
        if (x.size() != dig.size())
            return dig.size() > x.size();
        for (int i = x.size() - 1; i >= 0; i--)
            if (x[i] != dig[i])
                return dig[i] > x[i];
        return 0;
    }

    bool operator<=(BigInt x)
    {
        (*this).rem();
        x.rem();
        if (sgn != x.sgn)
            return sgn < x.sgn;
        if (x.size() != dig.size())
            return dig.size() < x.size();
        for (int i = x.size() - 1; i >= 0; i--)
            if (x[i] != dig[i])
                return dig[i] < x[i];
        return 1;
    }

    bool operator>=(BigInt x)
    {
        (*this).rem();
        x.rem();
        if (sgn != x.sgn)
            return sgn > x.sgn;
        if (x.size() != dig.size())
            return dig.size() > x.size();
        for (int i = x.size() - 1; i >= 0; i--)
            if (x[i] != dig[i])
                return dig[i] > x[i];
        return 1;
    }

    bool operator==(BigInt x)
    {
        (*this).rem();
        x.rem();
        return sgn == x.sgn && dig == x.dig;
    }

    bool operator!=(BigInt x)
    {
        (*this).rem();
        x.rem();
        return sgn != x.sgn || dig != x.dig;
    }

    BigInt operator-() const
    {
        BigInt ret = (*this);
        ret.sgn = -sgn;
        return ret;
    }

    void assign(int k, ll zn = 0)
    {
        dig.assign(k, zn);
    }

    void resize(int k)
    {
        while (dig.size() < k)
            dig.push_back(0);
    }

    BigInt operator-(BigInt x)
    {
        x.rem();
        (*this).rem();
        if (x.sgn == 0)
            return (*this);
        if (sgn == 0)
            return (-x);
        if (sgn != x.sgn)
        {
            if (sgn == 1)
                return ((*this) + (-x));
            else
                return (x + (-(*this)));
        }
        bool rev = 0;
        if (sgn == -1)
        {
            sgn = 1;
            x.sgn = 1;
            rev = 1;
        }
        if ((*this) < x)
        {
            if (rev)
            {
                sgn = -1;
                x.sgn = -1;
            }
            return -(x - (*this));
        }
        BigInt ans;
        ans.assign(max(x.size(), (int)dig.size()));
        for (int i = 0; i < ans.size(); i++)
            ans.dig[i] = dig[i] - x[i];
        for (int i = 0; i < ans.size(); i++)
        {
            if (ans[i] < 0)
            {
                ans.dig[i] += B;
                ans.dig[i + 1]--;
            }
        }
        if (rev)
        {
            sgn = -1;
            x.sgn = -1;
        }
        ans.sgn = sgn;
        ans.rem();
        return ans;
    }

    BigInt operator+(BigInt x)
    {
        x.rem();
        (*this).rem();
        if (x.sgn == 0)
            return (*this);
        if (sgn == 0)
            return x;
        if (sgn != x.sgn)
        {
            if (sgn == 1)
                return ((*this) - (-x));
            else
                return (x - (-(*this)));
        }
        BigInt ans;
        ans.assign(max(x.size(), (int)dig.size()) + 1);
        for (int i = 0; i < ans.size(); i++)
            ans.dig[i] = x[i] + dig[i];
        for (int i = 0; i + 1 < ans.size(); i++)
        {
            if (ans[i] >= B)
            {
                ans.dig[i] -= B;
                ans.dig[i + 1]++;
            }
        }
        ans.sgn = sgn;
        ans.rem();
        return ans;
    }

    void operator+=(BigInt x)
    {
        (*this) = (*this) + x;
    }

    void operator-=(BigInt x)
    {
        (*this) = (*this) - x;
    }

    BigInt operator+(ll x)// TODO NEED TO BE UPGRADED
    {
        return (*this) + BigInt(x);
    }

    BigInt operator-(ll x)
    {
        return (*this) - BigInt(x);
    }

    void operator+=(ll x)
    {
        (*this) = (*this) + BigInt(x);
    }

    void operator-=(ll x)
    {
        (*this) = (*this) - BigInt(x);
    }

    BigInt operator*(BigInt x)
    {
        x.rem();
        (*this).rem();
        BigInt ans;
        ans.assign(x.size() + dig.size() + 1);
        for (int i = 0; i < x.size(); i++)
            for (int j = 0; j < dig.size(); j++)
                ans.dig[i + j] += x[i] * dig[j];
        ans.sgn = x.sgn * sgn;
        ans.rem();
        return ans;
    }

    void operator*=(BigInt x)
    {
        (*this) = (*this) * x;
    }

    BigInt operator*(ll x)
    {
        return (*this) * BigInt(x);
    }

    void operator*=(ll x)
    {
        (*this) = (*this) * BigInt(x);
    }

    BigInt operator|(BigInt x)
    {
        //TODO (FFT multiplication)
        cerr << "BigInt: fft multiplication with | isn't implemented yet" << endl;
        exit(0);
        return x;
    }

    void operator|=(BigInt x)
    {
        cerr << "BigInt: fft multiplication with |= isn't implemented yet" << endl;
        exit(0);

        //TODO (FFT multiplication)
    }

    BigInt operator/(ll x)
    {
        if (x == 0)
        {
            cerr << "BigInt: dividing by short zero" << endl;
            exit(0);
        }
        ll carry = 0;
        BigInt ans;
        ans.assign(dig.size());
        for (int i = (int)dig.size() - 1; i >= 0; i--)
        {
            carry = carry * B + dig[i];
            ans.dig[i] = carry / x;
            carry %= x;
        }
        ans.rem();
        return ans;
    }

    void operator/=(ll x)
    {
        (*this) = (*this) / x;
    }

    BigInt operator/(BigInt x)
    {
        x.rem();
        (*this).rem();
        if (x.sgn == 0)
        {
            cerr << "BigInt: dividing by big zero" << endl;
            exit(0);
        }
        if (sgn == 0)
            return (*this);
        int newsgn = sgn * x.sgn;
        BigInt a = (*this);
        a.sgn = 1;
        BigInt b = x;
        b.sgn = 1;
        BigInt l(0), r = a + 1;
        while (l + 1 != r)
        {
            BigInt mid = (r + l) / 2;
            if (mid * b > a)
                r = mid;
            else
                l = mid;
        }
        return l;
    }

    void operator/=(BigInt x)
    {
        (*this) = (*this) / x;
    }

    BigInt operator%(BigInt x)
    {
        return (*this) - ((*this) / x) * x;
    }

    void operator %=(BigInt x)
    {
        (*this) = (*this) % x;
    }

    BigInt operator^(ll k) // power
    {
        if (k < 0)
            return BigInt(0);
        if (!k)
            return BigInt(1);
        BigInt ans = (*this);
        vector<int> a;
        while (k)
        {
            a.push_back(k % 2);
            k /= 2;
        }
        a.pop_back();
        reverse(a.begin(), a.end());
        for (int i : a)
        {
            ans *= ans;
            if (i)
                ans *= (*this);
        }
        return ans;
    }

    void operator^=(ll k)
    {
        (*this) = ((*this) ^ k);
    }
};

BigInt factorial(int x)
{
    BigInt ans(1);
    for (int i = 2; i <= x; i++)
        ans *= (ll)i;
    return ans;
}

BigInt Sqrt(BigInt x)
{
    x.rem();
    if (x.sgn == -1)
    {
        cout << "BigInt trying to take sqrt of negative number" << endl;
        exit(0);
    }
    if (x.sgn == 0)
        return x;
    BigInt l = 0, r = x + 1;
    while (l + 1 != r)
    {
        BigInt mid = (r + l) / 2;
        if (mid * mid > x)
            r = mid;
        else
            l = mid;
    }
    return l;
}