struct BigInt {
	lls a[maxn]; int len;
	BigInt() : len(0) { memset(a,0,sizeof(a)); }
	BigInt(int x) : len(1) { memset(a,0,sizeof(a)); a[1]=x; }
	inline void print() {
		printf("%lld",a[len]);
		for(re int i=len-1;i>=1;i--) printf("%016lld",a[i]);
		puts("");
	}
	bool operator < ( const BigInt & b ) const {
		if(len!=b.len) return len<b.len;
		for(re int i=len;i>=1;i--) if(a[i]!=b.a[i]) return a[i]<b.a[i];
		return false;
	}
	BigInt operator + ( const BigInt & b ) const {
		BigInt c; c.len=max(len,b.len)+1;
		int d=0;
		for(re int i=1;i<=c.len;i++) {
			c.a[i]=a[i]+b.a[i]+d; 
			d=c.a[i]/asd; 
			c.a[i]%=asd; 
		}
		while(c.len>1&&c.a[c.len]==0) --c.len;
		return c ;
	}
	BigInt operator - ( const int & b ) const {
		BigInt c=(*this); c.a[1]-=b; 
		for(re int i=1;i<=c.len;i++) {
			if(c.a[i]<0) c.a[i]+=asd,--c.a[i+1];
		}
		while(c.len>1&&c.a[c.len]==0) --c.len;
		return c ;
	}
	BigInt operator * ( const int & b ) const {
		BigInt c; c.len=len+1;
		for(re int i=1;i<=c.len;i++) {
			c.a[i]+=a[i]*b;
			c.a[i+1]+=c.a[i]/asd;
			c.a[i]%=asd;
		}
		while(c.len>1&&c.a[c.len]==0) --c.len;
		return c ;
	}
	BigInt operator / ( const int & b ) const {
		BigInt c=(*this); c.len=len;
		for(re int i=len;i>=1;i--) {
			c.a[i-1]+=c.a[i]%b*asd;
			c.a[i]/=b;
		}
		while(c.len>1&&c.a[c.len]==0) --c.len;
		return c;
	}
}  ; 
BigInt read() {
	char c[maxn];
	scanf("%s",c+1); BigInt res; 
	for(re int i=1,n=strlen(c+1);i<=n;i++) {
		res=res*10+(c[i]-'0');
	}
	return res;
}