蒟蒻发电嗨起来，神犇AK IOI

FarmerJohn他已出现，FarmerJohn他要发电

同学上课玩游戏 老师翻车没实力

上课还要听个 P，信息队快要倒闭（ohohoh）

自信递交太着急，九个WA+TLE

每周都要打比赛，排名不倒数才怪（copy right）

同学开挂要上天，老师立马变神仙

顶级大佬去跳伞 ~ 信息队就要完蛋 ~~~

信息队很快就要解散，解散！！！

$$高精度模板（竞赛别用）$$

struct BigInt {
int n;     // 大整数的长度
int a[N];  // 大整数每一位
int f;     // f = 1: 0和正数; f = -1: 负数
// BigInt(int x) {
//     n = 0;
//     while (x != 0) a[n++] = x % 10, x /= 10;        
// }void set(int x) {
    f = (x >= 0 ? 1 : -1), x = abs(x);
    n = 0;
    while (x != 0) a[n++] = x % 10, x /= 10;
}

void set(string s) {
	f = (s[0] == '-' ? -1 : 1);
	n = 0;
	for (int i = (int) s.size() - 1; i >= (f == -1 ? 1 : 0); i--) a[n++] = s[i] - '0';
}

BigInt& operator =(BigInt x) {
    n = x.n;
    for (int i = 0; i < n; i++) a[i] = x.a[i];
    return *this;
}void arrange() {
    // 2、确定符号
    f = 1;
    for (int i = n - 1; i >= 0; i--) if (a[i] != 0) {
        f = (a[i] >= 0 ? 1 : -1);
        break;
    }

    // 3、进位或者借位
    int d = 0;
    for (int i = 0; i < n; i++) {
        int sum = d + f * a[i];  // 一定要乘以 f
        d = sum / 10;
        a[i] = sum % 10;
        if (a[i] < 0) a[i] += 10, d--;
    }

    // 加法多一位, 减法去除前导 0
    if (d > 0) a[n++] = d;
    while (n > 1 && a[n - 1] == 0) n--;

}

BigInt operator +(BigInt x) {
    BigInt ans;
    ans.n = max(n, x.n);    // 1、按位 + -
    for (int i = 0; i < ans.n; i++) ans.a[i] = 0;
    for (int i = 0; i < n; i++) ans.a[i] += f * a[i];
    for (int i = 0; i < x.n; i++) ans.a[i] += x.f * x.a[i];
    ans.arrange();

    return ans;
}

BigInt operator -(BigInt x) {
    BigInt y = x;
    y.f = 0 - y.f;  // 1 => -1; -1 => 1
    return *this + y;
}

BigInt operator *(BigInt x) {
    BigInt ans;
    ans.n = n + x.n - 1;

    // 1、按位 + -
    for (int i = 0; i < ans.n; i++) ans.a[i] = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < x.n; j++) {
        ans.a[i + j] += f * a[i] * x.f * x.a[j];
    }  
    ans.arrange();

    return ans; 
}BigInt operator *(int x) {
    BigInt y;
    y.set(x);
    return *this * y; 
}

BigInt operator /(int x) {
    BigInt ans;
    ans.n = n;
    
    int d = 0;
    for (int i = n - 1; i >= 0; i--) {
        d = d * 10 + a[i];
        ans.a[i] = d / x;
        d = d % x;
    }        
    while (ans.n > 1 && ans.a[ans.n - 1] == 0) ans.n--;
    return ans; 
}

int operator %(int x) {
    BigInt ans;
    ans.n = n;
int d = 0;
for (int i = n - 1; i >= 0; i--) {
d = d * 10 + a[i];
ans.a[i] = d / x;
d = d % x;
}
return d;
}

void print() {
if (f == -1) cout << '-';
for (int i = n - 1; i >= 0; i--) cout << a[i];
cout << '\n';
}

};