#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct bign {
#define maxn 10000
#define yawei 4
#define base 10000
int num[maxn],len;
bool flag;
friend bign abs(const bign &x) {
bign k=x;
k.flag=1;
return k;
}
friend void remove(bign &x) {
while(x.num[x.len]==0&&x.len>1)x.len--;
}
bign() {
memset(num,0,sizeof(num));
flag=1;
len=1;
}
bign(const int &x) {
*this=bign();
if(x) {
int k=x;
if(k<0)k=-k,flag=0;
len=0;
while(k) {
num[++len]=k%base;
k/=base;
}
}
}
bign(const char *x) {
int l=strlen(x),s,t=0,p=0,k=1;
*this=bign();
if(x[0]=='-')flag=0,s=1;
len=0;
for(int i=l-1; i>=s; i--) {
p+=k*(x[i]-'0');
k*=10;
t++;
if(t==4) {
t=0;
num[++len]=p;
p=0;
k=1;
}
}
if(p)num[++len]=p;
}
bign(const string x) {
int l=x.length(),s=0,t=0,p=0,k=1;
*this=bign();
if(x[0]=='-')flag=0,s=1;
len=0;
for(int i=l-1; i>=s; i--) {
p+=k*(x[i]-'0');
k*=10;
t++;
if(t==yawei) {
t=0;
num[++len]=p;
p=0;
k=1;
}
}
if(p)num[++len]=p;
}
bign operator = (const int &x) {
return *this=bign(x);
}
bign operator = (const char *x) {
return *this=bign(x);
}
bign operator = (const string &x) {
return *this=bign(x);
}
bool operator < (const bign &x)const {
if(flag!=x.flag)return flag<x.flag;
if(len!=x.len)return (len<x.len)^flag^1;
for(int i=len; i>=1; i--) {
if(num[i]!=x.num[i]) {
return (num[i]<x.num[i])^flag^1;
}
}
return 0;
}
bool operator < (const int &x)const {
return *this<bign(x);
}
bool operator > (const bign &x)const {
return x<*this;
}
bool operator > (const int &x)const {
return *this>bign(x);
}
bool operator <= (const bign &x)const {
return !(*this>x);
}
bool operator <= (const int &x)const {
return *this<=bign(x);
}
bool operator >= (const bign &x)const {
return !(*this<x);
}
bool operator >= (const int &x)const {
return *this>=bign(x);
}
bool operator == (const bign &x)const {
if(flag!=x.flag)return 0;
if(len!=x.len)return 0;
for(int i=len; i>=1; i--) {
if(num[i]!=x.num[i]) {
return 0;
}
}
return 1;
}
bool operator == (const int &x)const {
return *this==bign(x);
}
bool operator != (const bign &x)const {
return !(*this==x);
}
bool operator != (const int &x)const {
return *this!=bign(x);
}
friend istream& operator >> (istream &in,bign &x) {
string s;
in>>s;
x=s;
return in;
}
friend ostream& operator << (ostream &out,const bign &x) {
if(x.flag==0)out<<"-";
out<<x.num[x.len];
for(int i=x.len-1; i>=1; i--)printf("%04d",x.num[i]);
return out;
}
bign operator - ()const {
bign k=*this;
k.flag^=1;
return k;
}
bign operator + (const bign &x)const {
if(flag&&x.flag) {
bign k=bign();
k.len=0;
for(int i=1,g=0; g||i<=len||i<=x.len; i++) {
int p=num[i]+x.num[i]+g;
k.num[++k.len]=p%base;
g=p/base;
}
return k;
}
if(flag&&!x.flag)return *this-(-x);
if(!flag&&x.flag)return x-(-*this);
return -((-x)+(-*this));
}
bign operator + (const int &x)const {
return *this+bign(x);
}
bign operator += (const bign &x) {
return *this=*this+x;
}
bign operator += (const int &x) {
return *this+=bign(x);
}
bign operator ++() {
return *this+=1;
}
bign operator ++(int) {
bign k=*this;
*this+=1;
return k;
}
bign operator - (const bign &x)const {
if(flag&&x.flag&&*this>=x) {
bign k=bign();
k.len=0;
for(int i=1,g=0; g||i<=len; i++) {
int p=num[i]-x.num[i]+g;
if(p<0)g=-1;
else g=0;
k.num[++k.len]=(p%base+base)%base;
}
remove(k);
return k;
}
if(flag&&x.flag)return -(x-*this);
if(flag&&!x.flag)return *this+(-x);
if(!flag&&x.flag)return -((-*this)+x);
return (-x)-(-*this);
}
bign operator -= (const bign &x) {
*this=*this-x;
return *this;
}
bign operator -= (const int &x) {
return *this-=bign(x);
}
bign operator -- () {
return *this-=1;
}
bign operator -- (int) {
bign k=*this;
*this-=1;
return k;
}
bign operator * (const bign &x)const {
bign k;
k.flag=(flag==x.flag);
k.len=len+x.len+1;
for(int i=1; i<=len; i++) {
for(int j=1; j<=x.len; j++) {
k.num[i+j-1]+=num[i]*x.num[j];
k.num[i+j]+=k.num[i+j-1]/base;
k.num[i+j-1]%=base;
}
}
remove(k);
return k;
}
bign operator * (const int &x)const {
bign k=bign();
k.len=0;
long long t[maxn];
for(int i=1;i<=len;i++)t[i]=num[i]*x;
for(int i=1,g=0;i<=len||g;i++){
k.num[++k.len]=(g+t[i])%base;
g=(g+t[i])/base;
}
return k;
}
bign operator *= (const bign &x) {
return *this=*this*x;
}
bign operator *= (const int &x) {
return *this=*this*x;
}
bign operator / (const bign &x)const {
if(x==0)return bign();
bign k=bign(),a=bign();
k.flag=(flag==x.flag);
k.len=len;
for(int i=len; i>=1; i--) {
a=a*base+num[i];
while(a>=abs(x)) {
a-=abs(x);
k.num[i]++;
}
}
remove(k);
return k;
}
bign operator / (const int &x)const {
if(x==0)return bign();
bign k=bign();
int a=0;
k.flag=(flag==(x>=0));
k.len=len;
for(int i=len; i>=1; i--) {
a=a*base+num[i];
k.num[i]=a/x;
a%=x;
}
remove(k);
return k;
}
bign operator /= (const bign &x) {
return *this=*this/x;
}
bign operator /= (const int &x) {
return *this=*this/x;
}
bign operator % (const bign &x)const {
if(x==0)return bign();
bign a=bign();
for(int i=len; i>=1; i--) {
a=a*base+num[i];
while(a>=abs(x))a-=abs(x);
}
if(a==0)return a;
if(flag&&x.flag)return a;
if(flag&&!x.flag)return a-abs(x);
if(!flag&&x.flag)return x-a;
return -a;
}
int operator % (const int &x)const {
if(x==0)return bign();
bign k=bign();
int a=0;
k.flag=(flag==(x>=0));
k.len=len;
for(int i=len; i>=1; i--) {
a=a*base+num[i];
k.num[i]=a/x;
a%=x;
}
return a;
}
bign operator %= (const bign &x) {
return *this=*this%x;
}
bign operator %= (const int &x) {
return *this=*this%bign(x);
}
friend bign pow(const bign &x,const bign &y) {
bign ans=1,cnt=x,w=y;
while(w>0) {
if(w%2==1)ans*=cnt;
cnt*=cnt;
w/=2;
}
return ans;
}
friend bign pow(const int &x,const bign &y) {
bign ans=1,cnt=x,w=y;
while(w>0) {
if(w%2==1)ans*=cnt;
cnt*=cnt;
w/=2;
}
return ans;
}
friend bign pow(const bign &x,const int &y) {
bign ans=1,cnt=x;
int w=y;
while(w) {
if(w&1)ans*=cnt;
cnt*=cnt;
w>>=1;
}
return ans;
}
friend bign powmod(const bign &x,const bign &y,const bign &z) {
bign ans=1,cnt=x,w=y;
while(w>0) {
if(w%2==1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w/=2;
}
return ans;
}
friend bign powmod(const int &x,const bign &y,const bign &z) {
bign ans=1,cnt=x,w=y;
while(w>0) {
if(w%2==1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w/=2;
}
return ans;
}
friend bign powmod(const bign &x,const int &y,const bign &z) {
bign ans=1,cnt=x;
int w=y;
while(w) {
if(w&1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w>>=1;
}
return ans;
}
friend bign powmod(const bign &x,const bign &y,const int &z) {
bign ans=1,cnt=x,w=y;
while(w>0) {
if(w%2==1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w/=2;
}
return ans;
}
friend bign powmod(const int &x,const bign &y,const int &z) {
bign ans=1,cnt=x,w=y;
while(w>0) {
if(w%2==1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w/=2;
}
return ans;
}
friend bign powmod(const bign &x,const int &y,const int &z) {
bign ans=1,cnt=x;
int w=y;
while(w) {
if(w&1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w>>=1;
}
return ans;
}
friend bign pow10mod(const bign &x,const bign &y,const int &mod) {
bign ans=1,cnt=x,w=y,z=pow(10,mod);
while(w>0) {
if(w%2==1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w/=2;
}
return ans;
}
friend bign pow10mod(const int &x,const bign &y,const int &mod) {
bign ans=1,cnt=x,w=y,z=pow(10,mod);
while(w>0) {
if(w%2==1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w/=2;
}
return ans;
}
friend bign pow10mod(const bign &x,const int &y,const int &mod) {
bign ans=1,cnt=x,z=pow(10,mod);
int w=y;
while(w) {
if(w&1)ans=ans*cnt%z;
cnt=cnt*cnt%z;
w>>=1;
}
return ans;
}
friend bign max(const bign &x,const bign &y){
return x>y?x:y;
}
friend bign min(const bign &x,const bign &y){
return x<y?x:y;
}
};
Processed:
0.009, SQL:
9
