template<int const_size> class small_int{
	public:
		int a[const_size];
		int fu;
		small_int(){
			to_empty();
			fu=0;
			siz=1;
		}
		int& operator [](const int x){
			return a[x];
		}
		small_int pub_int(long long x){
			small_int<const_size> c;
			if(x<0) c.fu=1,x=-x;
			int cnt=-1;
			if(x==0){
				c.siz=1;
				return c;
			}
			while(x>0){
				c[++cnt]=x%10;
				x/=10;
			}
			c.siz=cnt+1;
			return c;
		}
		void out(const string s="\n"){
			if(siz==1 && a[0]==0) {cout<<0<<s;return ;}
			if(fu) cout<<"-";
			for(int i=siz-1;i>=0;--i) cout<<a[i];
			cout<<s;
			return ;
		}
		int size(){
			return siz;
		} 
		void to_empty(){
			for(int i=0;i<const_size;++i) a[i]=0;
			siz=0;
			fu=0;
			return ;
		}
		void in(){
			string s;
			cin>>s;
			bool flag=0;
			if(s[0]=='-') fu=1,s=s.substr(1,s.length()-1);
			int len=s.length();
			to_empty();
			for(int i=0,j=len-1;i<len;++i,--j) a[i]=s[j]-'0',flag=(a[i]!='0' ? 1 : flag);
			--len;
			while(len>0 && a[len]==0) --len;
			siz=len+1;
			if(!flag) fu=0,siz=1;
			return ;
		}
		void duru(string s){
			bool flag=0;
			if(s[0]=='-') fu=1,s=s.substr(1,s.length()-1);
			int len=s.length();
			to_empty();
			for(int i=0,j=len-1;i<len;++i,--j) a[i]=s[j]-'0',flag=(a[i]!='0' ? 1 : flag);
			--len;
			while(len>0 && a[len]==0) --len;
			siz=len;
			if(!flag) fu=0,siz=1;
			return ;
		}
		small_int operator + (small_int b){
			small_int<const_size> c;
			int up=min(max(siz,b.siz)+1,const_size);
			if(fu==1 && b.fu==1){
				c.fu=1;
				for(int i=0;i<up;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10,c.siz=max(c.siz,i+2);
					if(c[i]>0) c.siz=max(c.siz,i+1);
				}
			}else if(fu==0 && b.fu==0){
				for(int i=0;i<up;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10,c.siz=max(c.siz,i+2);
					if(c[i]>0) c.siz=max(c.siz,i+1);
				}
			}else{
				small_int<const_size> c,d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				c=(fu==1 && b.fu==0 ? b-d : d-b);
			}
			return c;
		}
		small_int operator + (long long B){
			small_int<const_size> b=pub_int(B);
			small_int<const_size> c;
			int up=min(max(b.siz,siz)+1,const_size);
			if(fu==1 && b.fu==1){
				c.fu=1;
				for(int i=0;i<up;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10,c.siz=max(c.siz,i+2);
					if(c[i]>0) c.siz=max(c.siz,i+1);
				}
			}else if(fu==0 && b.fu==0){
				for(int i=0;i<up;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10,c.siz=max(c.siz,i+2);
					if(c[i]>0) c.siz=max(c.siz,i+1);
				}
			}else{
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				c=(fu==1 && b.fu==0 ? b-d : d-b);
			}
			return c;
		}
		//  1234567
		// -1208396
		bool operator > (small_int b){
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 0;
					if(a[i]>b[i]) return 1;
				}
				return 0;
			}else{
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 1;
					if(a[i]>b[i]) return 0;
				}
				return 0;
			}
		}
		bool operator > (long long B){
			small_int<const_size> b=pub_int(B);
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 0;
					if(a[i]>b[i]) return 1;
				}
				return 0;
			}else{
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 1;
					if(a[i]>b[i]) return 0;
				}
				return 0;
			}
		}
		bool operator >= (small_int b){
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 0;
					if(a[i]>b[i]) return 1;
				}
				return 1;
			}else{
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 1;
					if(a[i]>b[i]) return 0;
				}
				return 1;
			}
		}
		bool operator >= (long long B){
			small_int<const_size> b=pub_int(B);
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 0;
					if(a[i]>b[i]) return 1;
				}
				return 1;
			}else{
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]<b[i]) return 1;
					if(a[i]>b[i]) return 0;
				}
				return 1;
			}
		}
		bool operator < (small_int b){
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 0;
					if(a[i]<b[i]) return 1;
				}
				return 0;
			}else{
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 1;
					if(a[i]<b[i]) return 0;
				}
				return 0;
			}
		}
		bool operator < (long long B){
			small_int<const_size> b=pub_int(B);
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 0;
					if(a[i]<b[i]) return 1;
				}
				return 0;
			}else{
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 1;
					if(a[i]<b[i]) return 0;
				}
				return 0;
			}
		}
		bool operator <= (small_int b){
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 0;
					if(a[i]<b[i]) return 1;
				}
				return 1;
			}else{
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 1;
					if(a[i]<b[i]) return 0;
				}
				return 1;
			}
		}
		bool operator <= (long long B){
			small_int<const_size> b=pub_int(B);
			if(fu==0 && b.fu==1) return 1;
			if(fu==1 && b.fu==0) return 0;
			if(b.fu==0 && fu==0){
				if(siz<b.siz) return 1;
				else if(siz>b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 0;
					if(a[i]<b[i]) return 1;
				}
				return 1;
			}else{
				if(siz>b.siz) return 1;
				else if(siz<b.siz) return 0;
				for(int i=const_size-1;i>=0;--i){
					if(a[i]>b[i]) return 1;
					if(a[i]<b[i]) return 0;
				}
				return 1;
			}
		}
		void swap(small_int &b){
			small_int<const_size> c;
			for(int i=0;i<const_size;++i) c[i]=b[i];
			for(int i=0;i<const_size;++i) b[i]=a[i];
			for(int i=0;i<const_size;++i) a[i]=c[i];
			return ;
		}
		bool operator == (small_int b){
			if(b.fu!=fu || siz!=b.siz) return 0;
			for(int i=const_size-1;i>=0;--i){
				if(a[i]!=b[i]) return 0;
			}
			return 1;
		}
		bool operator == (long long B){
			small_int<const_size> b=B;
			if(b.fu!=fu || siz!=b.siz) return 0;
			for(int i=const_size-1;i>=0;--i){
				if(a[i]!=b[i]) return 0;
			}
			return 1;
		}
		small_int operator - (long long B){
			small_int<const_size> b=pub_int(B);
			small_int<const_size> c;
			if(fu==0 && b.fu==0){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				if(b>d) d.swap(b),c.fu=1;
				for(int i=0;i<const_size;++i){
					c[i]+=d[i]-b[i];
					if(c[i]<0){
						if(i+1<const_size) c[i]+=10,--c[i+1];
					}
				}
				int i=const_size-1;
				while(i>0 && c[i]<=0) --i;
				c.siz=i+1;
			}else if(fu==0 && b.fu==1){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				b.fu=0;
				c=d+b;
			}else if(fu==1 && b.fu==1){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				b.fu=0;
				c=b-d;
			}else if(fu==1 && b.fu==0){
				small_int<const_size> d,e;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				d.fu=1;
				b.fu=1;
				c=b+d;
			}
			return c;
		}
		small_int operator - (small_int b){
			small_int<const_size> c;
			if(fu==0 && b.fu==0){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				if(b>d) d.swap(b),c.fu=1;
				for(int i=0;i<const_size;++i){
					c[i]+=d[i]-b[i];
					if(c[i]<0){
						if(i+1<const_size) c[i]+=10,--c[i+1];
					}
				}
				int i=const_size-1;
				while(i>0 && c[i]<=0) --i;
				c.siz=i+1;
			}else if(fu==0 && b.fu==1){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				b.fu=0;
				c=d+b;
			}else if(fu==1 && b.fu==1){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				b.fu=0;
				c=b-d;
			}else if(fu==1 && b.fu==0){
				small_int<const_size> d,e;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				d.siz=siz;
				d.fu=1;
				b.fu=1;
				c=b+d;
			}
			return c;
		}
		small_int operator * (small_int b){
			small_int<const_size> c;
			if(fu==1 && b.fu==1 || fu==0 && b.fu==0){
				int upi=min(siz+1,const_size),upj=min(b.siz+1,const_size);
				for(int i=0;i<upi;++i){
					if(a[i]==0) continue;
					for(int j=0;j<upj;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>0) c.siz=max(c.siz,i+j+1);
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10,c.siz=max(c.siz,i+j+2);
							c[i+j]%=10;
						}
					}
				}
			}else{
				c.fu=1;
				int upi=min(siz+1,const_size),upj=min(b.siz+1,const_size);
				for(int i=0;i<upi;++i){
					if(a[i]==0) continue;
					for(int j=0;j<upj;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>0) c.siz=max(c.siz,i+j+1);
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10,c.siz=max(c.siz,i+j+2);
							c[i+j]%=10;
						}
					}
				}
			}
			return c;
		}
		small_int operator * (long long B){
			small_int<const_size> b=pub_int(B);
			small_int<const_size> c;
			if(fu==1 && b.fu==1 || fu==0 && b.fu==0){
				int upi=min(siz+1,const_size),upj=min(b.siz+1,const_size);
				for(int i=0;i<upi;++i){
					if(a[i]==0) continue;
					for(int j=0;j<upj;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>0) c.siz=max(c.siz,i+j+1);
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10,c.siz=max(c.siz,i+j+2);
							c[i+j]%=10;
						}
					}
				}
			}else{
				c.fu=1;
				int upi=min(siz+1,const_size),upj=min(b.siz+1,const_size);
				for(int i=0;i<upi;++i){
					if(a[i]==0) continue;
					for(int j=0;j<upj;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>0) c.siz=max(c.siz,i+j+1);
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10,c.siz=max(c.siz,i+j+2);
							c[i+j]%=10;
						}
					}
				}
			}
			return c;
		}
		small_int operator / (long long b){
			small_int<const_size> c,A;
			for(int i=0;i<const_size;++i) A[i]=a[i];
			A.siz=siz;
			if((int)fu+(b<0)==1) c.fu=1;
			if(b<0) b=-b;
			long long yu=0;
			for(int i=min(A.siz,const_size-1);i>=0;--i){
				yu=yu*10+A[i];
				c[i]=yu/b;
				if(c[i]>0 && c.siz==1) c.siz=i+1;
				yu%=b;
			}
			return c;
		}
		long long operator % (long long b){
			small_int<const_size> A;
			for(int i=0;i<const_size;++i) A[i]=a[i];
			A.siz=siz;
			if(b<0) b=-b;
			long long yu=0;
			for(int i=min(A.siz,const_size-1);i>=0;--i){
				yu=yu*10+A[i];
				yu%=b;
			}
			return yu;
		}
		small_int operator / (small_int b){
			small_int<const_size> yu;
			small_int<const_size> c,A;
			for(int i=0;i<const_size;++i) A[i]=a[i];
			A.siz=siz;
			if((int)fu+(int)b.fu==1) c.fu=1;
			b.fu=0;
			for(int i=min(A.siz,const_size-1);i>=0;--i){
				yu.fast_multiply(1);
				yu=yu+A[i];
				if(yu>=b){
					long long l=1,r=9;
					while(l<=r){
						long long mid=(l+r)>>1;
						if(yu>=b*mid) l=mid+1; // r=ans
						else r=mid-1;
					}
					c[i]=r;
					yu=yu-b*r;
					if(c[i]>0 && c.siz==1) c.siz=i+1;
				}
			}
			return c;
		}
		small_int operator % (small_int b){
			small_int<const_size> yu;
			small_int<const_size> A;
			for(int i=0;i<const_size;++i) A[i]=a[i];
			A.siz=siz;
			for(int i=min(A.siz,const_size-1);i>=0;--i){
				yu.fast_multiply(1);
				yu=yu+A[i];
				if(yu>=b){
					long long l=1,r=9;
					while(l<=r){
						long long mid=(l+r)>>1;
						if(yu>=b*mid) l=mid+1; // r=ans
						else r=mid-1;
					}
					yu=yu-b*r;
				}
			}
			return yu;
		}
		void operator = (small_int o){
			for(int i=0;i<const_size;++i) a[i]=o[i];
			fu=o.fu;
			siz=o.siz;
			return ;
		}
		void operator = (long long o){
			small_int<const_size> b=pub_int(o);
			for(int i=0;i<const_size;++i) a[i]=b[i];
			fu=b.fu;
			siz=b.siz;
			return ;
		}
		small_int pub_max(small_int a,small_int b){
			if(a>b) return a;
			return b;
		}
		small_int pub_min(small_int a,small_int b){
			if(a<b) return a;
			return b;
		}
	private:
		int siz;
		void fast_multiply(int x){
			for(int i=min(const_size-1,siz+x-1);i>=x;--i) a[i]=a[i-x];
			for(int i=x-1;i>=0;--i) a[i]=0;
			return ;
		}
};