template<int const_size> class small_int{
	public:
		int a[const_size],fu;
		small_int(){
			to_empty();
			fu=0;
		}
		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;
			while(x>0){
				c[++cnt]=x%10;
				x/=10;
			}
			return c;
		}
		void out(const string s="\n"){
			int i=const_size-1;
			while(i>0 && a[i]==0) --i;
			if(i==0 && a[i]==0){
				cout<<0;
				cout<<s;
				return ;
			}
			if(fu) cout<<"-";
			for(;i>=0;--i) cout<<a[i];
			cout<<s;
			return ;
		}
		int size(){
			int n=const_size-1;
			while(n>0 && a[n]==0) --n;
			return n+1;
		} 
		void to_empty(){
			for(int i=0;i<const_size;++i) a[i]=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);
			if(!flag) fu=0;
			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);
			if(!flag) fu=0;
			return ;
		}
		small_int operator + (small_int b){
			small_int<const_size> c;
			if(fu==1 && b.fu==1){
				c.fu=1;
				for(int i=0;i<const_size;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10;
				}
			}else if(fu==0 && b.fu==0){
				for(int i=0;i<const_size;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10;
				}
			}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;
			if(B<0) b.fu=1,B=-B;
			int cnt=-1;
			while(B>0){
				b[++cnt]=B%10;
				B/=10;
			}
			small_int<const_size> c;
			if(fu==1 && b.fu==1){
				c.fu=1;
				for(int i=0;i<const_size;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10;
				}
			}else if(fu==0 && b.fu==0){
				for(int i=0;i<const_size;++i){
					c[i]+=a[i]+b[i];
					if(c[i]>=10 && i+1<const_size) ++c[i+1],c[i]-=10;
				}
			}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;
		}
		//  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){
				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{
				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){
				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{
				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){
				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{
				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){
				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{
				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){
				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{
				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){
				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{
				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){
				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{
				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){
				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{
				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) 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) 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;
			if(B<0) b.fu=1,B=-B;
			int cnt=-1;
			while(B>0){
				b[++cnt]=B%10;
				B/=10;
			}
			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];
				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];
					}
				}
			}else if(fu==0 && b.fu==1){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				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];
				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.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];
				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];
					}
				}
			}else if(fu==0 && b.fu==1){
				small_int<const_size> d;
				for(int i=0;i<const_size;++i) d[i]=a[i];
				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];
				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.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){
				for(int i=0;i<const_size;++i){
					if(a[i]==0) continue;
					for(int j=0;j<const_size;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10;
							c[i+j]%=10;
						}
					}
				}
			}else{
				c.fu=1;
				for(int i=0;i<const_size;++i){
					if(a[i]==0) continue;
					for(int j=0;j<const_size;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10;
							c[i+j]%=10;
						}
					}
				}
			}
			return c;
		}
		small_int operator * (long long B){
			small_int<const_size> b;
			if(B<0) b.fu=1,B=-B;
			int cnt=-1;
			while(B>0){
				b[++cnt]=B%10;
				B/=10;
			}
			small_int<const_size> c;
			if(fu==1 && b.fu==1 || fu==0 && b.fu==0){
				for(int i=0;i<const_size;++i){
					if(a[i]==0) continue;
					for(int j=0;j<const_size;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10;
							c[i+j]%=10;
						}
					}
				}
			}else{
				c.fu=1;
				for(int i=0;i<const_size;++i){
					if(a[i]==0) continue;
					for(int j=0;j<const_size;++j){
						if(i+j>=const_size) break;
						c[i+j]+=a[i]*b[j];
						if(c[i+j]>=10){
							if(i+j+1<const_size) c[i+j+1]+=c[i+j]/10;
							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];
			if((int)fu+(b<0)==1) c.fu=1;
			if(b<0) b=-b;
			long long yu=0;
			for(int i=const_size-1;i>=0;--i){
				yu=yu*10+A[i];
				c[i]=yu/b;
				yu%=b;
			}
			return c;
		}
		long long operator % (long long b){
			small_int<const_size> c,A;
			for(int i=0;i<const_size;++i) A[i]=a[i];
			if((int)fu+(b<0)==1) c.fu=1;
			if(b<0) b=-b;
			long long yu=0;
			for(int i=const_size-1;i>=0;--i){
				yu=yu*10+A[i];
				c[i]=yu/b;
				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];
			if((int)fu+(int)b.fu==1) c.fu=1;
			b.fu=0;
			for(int i=const_size-1;i>=0;--i){
				yu=yu*10+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;
				}
			}
			return c;
		}
		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];
			if((int)fu+(int)b.fu==1) c.fu=1;
			b.fu=0;
			for(int i=const_size-1;i>=0;--i){
				yu=yu*10+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;
				}
			}
			return yu;
		}
		void operator = (small_int o){
			for(int i=0;i<const_size;++i) a[i]=o[i];
			fu=o.fu;
			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;
			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;
		}
};