namespace _BigInt {
using i64 = long long;
vector<int> pow2 = []() -> vector<int> {
vector<int> pow2(31);
pow2[0] = 1;
for (int i = 1 ; i <= 30 ; i++) {
pow2[i] = pow2[i - 1] * 2;
}
return pow2;
}();
struct BigInt {
static const int BASE = 100000000;
static const int WIDTH = 8;
bool sign = true;
vector<int> num;
BigInt() : num(1), sign(true) {}
BigInt(int x) {
if (x < 0) {
x = -x;
sign = false;
}
do {
num.push_back(x % BASE);
x /= BASE;
} while (x);
check(*this);
}
BigInt(i64 x) {
if (x < 0) {
x = -x;
sign = false;
}
do {
num.push_back(x % BASE);
x /= BASE;
} while (x);
check(*this);
}
BigInt(string x) {
reverse(begin(x), end(x));
if (x.back() == '-') {
sign = false;
x.pop_back();
}
int len = x.size();
len = (len + WIDTH - 1) / WIDTH;
x.resize(len * WIDTH, '0');
for (int i = 0 ; i < len ; i++) {
int res = 0;
for (int j = (i + 1) * WIDTH - 1 ; j >= i * WIDTH ; j--) {
res = res * 10 + (x[j] - '0');
}
num.push_back(res);
}
check(*this);
}
friend BigInt operator+(BigInt x, BigInt y) {
if (x.sign != y.sign) {
x.sign = !x.sign;
return x - y;
};
int len = max(x.size(), y.size());
x.resize(len); y.resize(len);
int k = 0;
for (int i = 0 ; i < len ; i++) {
x[i] += y[i] + k;
k = 0;
if (x[i] >= BASE) {
k = 1;
x[i] -= BASE;
}
}
if (k) x.push_back(k);
return check(x), x;
}
friend BigInt operator-(BigInt x, BigInt y) {
if (x.sign != y.sign) {
x.sign = !x.sign;
return x + y;
}
if (abs_equal(x, y) == -1) {
swap(x, y);
x.sign = !x.sign;
}
int len = max(x.size(), y.size());
x.resize(len); y.resize(len);
int k = 0;
for (int i = 0 ; i < len ; i++) {
x[i] -= y[i] + k;
k = 0;
if (x[i] < 0) {
x[i] += BASE;
k = 1;
}
}
while (x.size() > 1 && x.back() == 0) {
x.pop_back();
}
return check(x), x;
}
friend BigInt operator*(BigInt x, BigInt y) {
int lenx = x.size(), leny = y.size();
BigInt res; res.resize(lenx + leny);
for (int i = 0 ; i < lenx ; i++) {
for (int j = 0 ; j < leny ; j++) {
i64 k = (i64) x[i] * y[j] + res[i + j];
res[i + j] = k % BASE;
res[i + j + 1] += k / BASE;
}
}
while (res.size() > 1 && res.back() == 0) {
res.pop_back();
}
return res.sign = x.sign == y.sign, check(res), res;
}
friend BigInt operator/(BigInt x, BigInt y) {
return Div(x, y).first;
}
friend BigInt operator%(BigInt x, BigInt y) {
return Div(x, y).second;
}
friend bool operator<(const BigInt &x, const BigInt &y) {
if (x.sign != y.sign) {
return x.sign == false;
}
int k = abs_equal(x, y);
return (x.sign == true && k == -1) || (x.sign == false && k == 1);
}
friend bool operator>(const BigInt &x, const BigInt &y) {
if (x.sign != y.sign) {
return x.sign == true;
}
int k = abs_equal(x, y);
return (x.sign == true && k == 1) || (x.sign == false && k == -1);
}
friend bool operator!=(const BigInt &x, const BigInt &y) {
return !(x == y);
}
friend bool operator==(const BigInt &x, const BigInt &y) {
int lenx = x.size(), leny = y.size();
if (lenx == leny) {
for (int i = lenx - 1 ; i >= 0 ; i--) {
if (x[i] == y[i]) continue;
return false;
}
return true;
}
return false;
}
friend BigInt& operator+=(BigInt &x, BigInt y) {
return x = x + y;
}
friend BigInt& operator-=(BigInt &x, BigInt y) {
return x = x - y;
}
friend BigInt& operator*=(BigInt &x, BigInt y) {
return x = x * y;
}
friend BigInt& operator/=(BigInt &x, BigInt y) {
return x = x / y;
}
friend BigInt& operator%=(BigInt &x, BigInt y) {
return x = x % y;
}
static pair<BigInt, BigInt> Div(BigInt x, BigInt y) {
int k = abs_equal(x, y);
if (k == 0) {
return {1, 0};
}
if (k == -1) {
return {0, x};
}
int len = x.size() - y.size() + 1;
BigInt q; q.resize(len);
BigInt r = x;
int z = __lg(BASE);
for (int i = len - 1 ; i >= 0 ; i--) {
BigInt t1; t1.resize(y.size() + i);
for (int j = 0 ; j < (int) y.size() ; j++) {
t1[j + i] = y[j];
}
for (int j = z ; j >= 0 ; j--) {
BigInt t2 = t1 * pow2[j];
if (abs_equal(r, t2) >= 0) {
q[i] += pow2[j];
r -= t2;
}
}
}
while (q.size() > 1 && q.back() == 0) {
q.pop_back();
}
check(q); check(r);
return {q, r};
}
// 比较绝对值大小
// -1 (x < y)
// 0 (x = y)
// 1 (x > y)
static int abs_equal(const BigInt &x, const BigInt &y) {
int lenx = x.size(), leny = y.size();
if (lenx == leny) {
for (int i = lenx - 1 ; i >= 0 ; i--) {
if (x[i] == y[i]) continue;
return x[i] < y[i] ? -1 : 1;
}
return 0;
}
return lenx < leny ? -1 : 1;
}
static void check(BigInt &x) {
if (x.size() == 1 && x.back() == 0) {
x.sign = true;
}
}
void print() const {
if (sign == false) cout << "-";
cout << num.back();
for (int i = (int) num.size() - 2 ; i >= 0 ; i--) {
cout << setfill('0') << setw(WIDTH) << num[i];
}
}
int& back() {
return num.back();
}
void pop_back() {
num.pop_back();
}
void push_back(int x) {
num.push_back(x);
}
void resize(int len) {
return num.resize(len);
}
int size() const {
return num.size();
}
int& operator[](int pos) {
return num[pos];
}
int operator[](int pos) const {
return num[pos];
}
friend istream& operator>>(istream &is, BigInt &x) {
string str;
is >> str;
return x = BigInt(str), is;
}
friend ostream& operator<<(ostream &os, const BigInt &x) {
return x.print(), os;
}
}; // BigInt
}
using _BigInt::BigInt;