const int maxn = 1e5 + 10;
struct BigInteger{
int len, num[maxn]; // maxn 要比数字最长可能长度大
// 在存储时是倒着存,从 1 开始
BigInteger(){len = 0; memset(num,0,sizeof num);}
BigInteger friend operator + (BigInteger a, BigInteger b){// 重载 + 运算符
BigInteger c;
c.len = 0;
int p1, p2; p1 = p2 = 1;
while(p1 <= a.len && p2 <= b.len){
c.num[++c.len] += a.num[p1++] + b.num[p2++];
if(c.num[c.len] >= 10) c.num[c.len+1]++, c.num[c.len] %= 10;
}
while(p1 <= a.len) {
c.num[++c.len] += a.num[p1++];
if(c.num[c.len] >= 10) c.num[c.len+1]++, c.num[c.len] %= 10;
}
while(p2 <= b.len) {
c.num[++c.len] += b.num[p2++];
if(c.num[c.len] >= 10) c.num[c.len+1]++, c.num[c.len] %= 10;
}
if(c.num[c.len+1] != 0) c.len++;
return c;
}
BigInteger friend operator - (BigInteger a, BigInteger b){// 重载 - 运算符
// a > b
for(int i=1;i<=b.len;i++){
if(a.num[i] >= b.num[i]){
a.num[i] -= b.num[i];
}else{
b.num[i] -= a.num[i];
a.num[i] = 0;
for(int j=i+1;j<=a.len;j++){
if(a.num[j] != 0){
a.num[j]--;
if(a.num[j] == 0 && j == a.len) a.len--;
for(int k=i;k<j;k++) a.num[k] = 9;
a.num[i] = 10 - b.num[i];
break;
}
}
}
}
return a;
}
BigInteger friend operator * (BigInteger a, BigInteger b){ // 重载 * 运算符
BigInteger c;
c.len = 1;
for(int i=1;i<=a.len;i++){
for(int j=1;j<=b.len;j++){
int pos = i+j-1;
c.num[pos] += a.num[i]*b.num[j];
if(c.num[pos] >= 10){
int add = c.num[pos]/10;
c.num[pos] %= 10;
c.num[pos+1] += add;
pos++;
}
c.len = max(c.len, pos);
}
}
for(int i=c.len;i>=1;i--) {
if(c.num[i] != 0) break;
c.len = i;
}
return c;
}
int compareTo(BigInteger b){
// 两数均 > 0
if(len > b.len) return 1; // b 较小
else if(len < b.len) return -1; // b 较大
for(int i=len;i>=1;i--) if(num[i] != b.num[i]) return num[i] > b.num[i] ? 1 : -1;
return 0; //相等
}
void mod(int p){ // 对 p 取模
int ans = 0;
for(int i=len;i>=1;i--){
ans = (ans * 10 + num[i]) % p;
}
get_int(ans);
}
int toInt(){ // 返回int
int ans = 0;
for(int i=len;i>=1;i--) ans = ans * 10 + num[i];
return ans;
}
char* toString(){ // 返回字符串
char *str = new char[100];
for(int i=1;i<=len;i++){
str[len-i+1] = num[i] +'0';
}
return str;
}
void print(){ // 输出
for(int i=len;i>=1;i--) printf("%d",num[i]);
printf("\n");
}
void get_str(char s[]){ // 将字符串变成大数
int l = strlen(s);
len = l;
for(int i=1;i<=l;i++){
num[i] = s[l-i]-'0';
}
}
void get_int(int n){ // 将整数变成大数
len = 1;
num[1] = n % 10;
n /= 10;
while(n){
num[++len] = n % 10;
n /= 10;
}
}
};