struct BigInt{
	int size=1;
	int f=1;
	int num[MAXNUM];
	BigInt(const BigInt &x){
		memcpy(num,x.num,sizeof(num));
		size=x.size;
		f=x.f;
	}
	BigInt(string s){
		memset(num,0,sizeof(num));
		while(s[0]=='0'&&s.size()>1) s=s.substr(1);
		size=s.size();
		for(int i=0;i<size;i++){
			num[size-i-1]=s[i]-'0';
		}
	}
	BigInt(int x=0){
		memset(num,0,sizeof(num));
		if(x==0){size=1;return;}
		size=0;
		while(x){
			num[size++]=x%10;
			x/=10;
		}
	}
	void prt(bool nl=false){
		if(f==-1) cout<<'-';
		for(int i=size-1;i>=0;i--) cout<<num[i];
		if(nl) cout<<"\n";
	}
	BigInt operator+(const BigInt b)const{
		BigInt c;
		int lenc=max(size,b.size);
		int jw=0;
		for(int i=0;i<lenc;i++){
			c.num[i]=num[i]+b.num[i]+jw;
			jw=c.num[i]/10;
			c.num[i]%=10;
		}
		if(jw) c.num[lenc++]=1;
		c.size=lenc;
		return c;
	}
	BigInt operator-(const BigInt b)const{
		BigInt c=*this,x=b;
		if(size<b.size){
			c=b;x=*this;
			c.f=-1;
		}else if(size==b.size){
			for(int i=size-1;i>=0;i--){
				if(num[i]<b.num[i]){
					c=b;x=*this;
					c.f=-1;
					break;
				}
			}
		}
		for(int i=0;i<c.size;i++){
			if(x.num[i]>c.num[i]){ 
				c.num[i+1]-=1;
				c.num[i]+=10;
			}
			c.num[i]=c.num[i]-x.num[i];
		}
		while(c.num[c.size-1]==0&&c.size>1) c.size--;
		return c;
	}
	BigInt operator/(const int b)const{
		BigInt c;
		int r=0;
		c.size=size;
		for(int i=size-1;i>=0;i--){
			r=r*10+num[i];
			c.num[i]=r/b;
			r%=b;
		}
		while(c.num[c.size-1]==0&&c.size>1) c.size--;
		return c;
	}
	BigInt operator*(const BigInt b)const{
		BigInt c;
		int lenc=size+b.size;
		int jw=0;
		for(int i=0;i<b.size;i++){
			for(int j=0;j<size;j++){
				c.num[i+j]+=b.num[i]*num[j];
			}
		}
		for(int i=0;i<lenc;i++){
			c.num[i+1]+=c.num[i]/10;
			c.num[i]%=10;
		}
		while(c.num[lenc-1]==0&&lenc>1) lenc--;
		c.size=lenc;
		return c;
	}
	BigInt operator%(const int b)const{
	    int r=0;
	    for(int i=size-1;i>=0;i--){ 
	    	r=r*10+num[i]; r%=b;
	    }
	    return r;
	}
};
//BigInt 非标准模板 

int jzhi(int x,string y){
    int h=0,ans=0,y2=0;
    if(x<=10){
        for(int i=0;i<y.size();i++){
            y2*=10;
            y2+=y[i]-'0';
        }
        while(y2){
            ans+=y2%10*pow(x,h);
            y2/=10;
            h++;
        }
    }else{
        for(int i=0;i<y.size();i++){
            y2*=10;
            if(y[i]>='0'&&y[i]<='9') y2+=y[i]-'0';
            else if(y[i]=='A') ans+=10*pow(x,i);
            else if(y[i]=='B') ans+=11*pow(x,i);
            else if(y[i]=='C') ans+=12*pow(x,i);
            else if(y[i]=='D') ans+=13*pow(x,i);
            else if(y[i]=='E') ans+=14*pow(x,i);
            else if(y[i]=='F') ans+=15*pow(x,i);
        }
    }
    return ans;
}
//2-16进制化十进制