__intinf

#include<bits/stdc++.h>
namespace std{
	class ZeroDivisionError:public exception{public:
	const char*what()const throw(){return "__intinf::divmod";}};
	class FFTLimitExceededError:public exception{public:
	const char*what()const throw(){return "__intinf::fft_mul";}};
	class __intinf{
	protected:
		using digit_t=long long;
		static constexpr int WIDTH=8;
		static constexpr digit_t BASE=1e8;
		static constexpr long long FFT_LIMIT=32;
		static constexpr long long NEWTON_LIMIT=128;
		static constexpr long long NEWTON_MIN_LEVEL=16;
		digit_t* digits;
		int capacity,size;
		bool flag;
		inline void push(const digit_t&);
		inline void pop();
		inline int compare(const __intinf&) const;	
		static inline __intinf fft_mul(const __intinf&,const __intinf&);
		__intinf newton_inv(int)const;
		inline pair<__intinf,__intinf>newton_div(const __intinf&)const;
		template<class F>inline static __intinf binary_op_helper(const __intinf&,const __intinf&,const F&);
	protected:
		inline void resize(const int&);
	public:
		inline void reserve(const int&);
		__intinf():digits(nullptr),flag(true){*this=0;}
		__intinf(const __intinf&x):digits(nullptr){*this=x;}
		__intinf(const long long&x):digits(nullptr){*this=x;}
		__intinf(const string&s):digits(nullptr){*this=s;}
		__intinf(const vector<bool>&b):digits(nullptr){*this=b;}
		template<class BoolIt>__intinf(const BoolIt& begin,const BoolIt& end):digits(nullptr)
		{*this=vector<bool>(begin,end);}
		__intinf&operator=(const __intinf&);
		__intinf&operator=(const long long&);
		__intinf&operator=(const string&);
		__intinf&operator=(const vector<bool>&);
		void clear();
		~__intinf(){clear();}
		friend ostream&operator<<(ostream&out,const __intinf&x){
			if(!x.flag)out<<'-';
			out<<(long long)x.digits[x.size];
			for(int i=x.size-1;i>=1;i--)
				out<<setw(WIDTH)<<setfill('0')<<(long long)x.digits[i];
			return out;
		}
		friend istream&operator>>(istream& in,__intinf& x){
			string s;in>>s;x=s; 
			return in;
		}
		string to_string()const;
		long long to_long_long()const;
		vector<bool>to_binary()const;
		int _digit_len()const;
		__intinf operator-()const;
		__intinf operator~()const;
		__intinf abs()const;
		static __intinf abs(const __intinf&);
		bool operator==(const __intinf&)const; 
	#if __cplusplus >= 202002L
		auto operator<=>(const __intinf&)const;
	#else
		bool operator<(const __intinf&)const;
		bool operator>(const __intinf&)const; 
		bool operator!=(const __intinf&)const;
		bool operator<=(const __intinf&)const;
		bool operator>=(const __intinf&)const;
	#endif
		__intinf div2()const;
		pair<__intinf,__intinf>divmod(const __intinf&,bool=false)const;
		__intinf operator+(const __intinf&)const;
		__intinf operator-(const __intinf&)const;
		__intinf operator*(const int&)const;
		__intinf operator*(const __intinf&)const;
		__intinf operator/(const long long&)const;
		__intinf operator/(const __intinf&)const;
		__intinf operator%(const long long&)const;
		__intinf operator%(const __intinf&)const;
		__intinf pow(const long long&)const;
		__intinf pow(const long long&,const __intinf&)const;
		__intinf root(const long long& =2)const;
		__intinf sqrt()const;
		__intinf gcd(const __intinf&)const;
		__intinf lcm(const __intinf&)const;
		static __intinf pow(const __intinf&,const long long&);
		static __intinf pow(const __intinf&,const long long&,const __intinf&);
		static __intinf root(const __intinf&,const long long&);
		static __intinf sqrt(const __intinf&);
		static __intinf gcd(const __intinf&,const __intinf&);
		static __intinf lcm(const __intinf&,const __intinf&);
		inline __intinf _move_l(int)const;
		inline __intinf _move_r(int)const;
		__intinf&operator+=(const __intinf&);
		__intinf&operator-=(const __intinf&);
		__intinf&operator*=(int);
		__intinf&operator*=(const __intinf&);
		__intinf&operator/=(const long long&);
		__intinf&operator/=(const __intinf&);
		__intinf&operator%=(const long long&);
		__intinf&operator%=(const __intinf&);
		__intinf operator<<(const long long&);
		__intinf operator>>(const long long&);
		__intinf&operator<<=(const long long&);
		__intinf&operator>>=(const long long&);
		__intinf operator&(const __intinf&);
		__intinf operator|(const __intinf&);
		__intinf operator^(const __intinf&);
		__intinf&operator&=(const __intinf&);
		__intinf&operator|=(const __intinf&);
		__intinf&operator^=(const __intinf&);
		__intinf&operator++();
		__intinf operator++(int);
		__intinf&operator--();
		__intinf operator--(int);
	};
	inline void __intinf::push(const digit_t&val){
		if(size==capacity){
			int new_capacity=0;
			if(capacity<256)new_capacity=capacity<<1;
			else new_capacity=std::pow(capacity+1,0.125)*capacity;
			digit_t* new_digits=new digit_t[new_capacity+1];
			memcpy(new_digits,digits,sizeof(long long)*(capacity+1));
			delete[] digits;
			digits=new_digits,capacity=new_capacity;
		}
		digits[++size]=val;
	}
	inline void __intinf::pop(){digits[size--]=0;}
	inline int __intinf::compare(const __intinf& x)const{
		if(flag&&!x.flag)return 1;
		if(!flag&&x.flag)return -1;
		int sgn=(flag&&x.flag?1:-1);
		if(size>x.size)return sgn;
		if(size<x.size)return -sgn;
		for(int i=size;i>=1;i--) {
			if(digits[i]>x.digits[i])return sgn;
			if(digits[i]<x.digits[i])return -sgn;
		}
		return 0;
	}
	inline void __intinf::reserve(const int&sz){
		if(sz<0)return;
		if(digits!=nullptr)delete[] digits;
		capacity=sz,size=0;
		digits=new digit_t[sz+1];
		memset(digits,0,sizeof(digit_t)*(sz+1));
	}
	inline void __intinf::resize(const int&sz){reserve(sz),size=sz;}
	__intinf&__intinf::operator=(const __intinf&x){
		reserve(x.size+1);
		flag=x.flag,size=x.size;
		memcpy(digits,x.digits,sizeof(digit_t)*(x.size+1));
		return *this;
	}
	__intinf&__intinf::operator=(const long long&x){
		flag=(x>=0),reserve(4);
		if(x==0)return size=1,digits[1]=0,*this;
		if(x==LLONG_MIN)return *this="-9223372036854775808";
		long long n=std::abs(x);
		do{push(n%BASE),n/=BASE;}while(n);
		return *this;
	}
	__intinf&__intinf::operator=(const string&s){
		flag=true,reserve(s.size()/WIDTH+1);
		if (s.empty()||s=="-")return *this=0;
		int i=0;if(s[0]=='-')flag=false,i++;
		for(int j=s.size()-1;j>=i;j-=WIDTH){
			int start=max(i,j-WIDTH+1),len=j-start+1;
			push(stoll(s.substr(start,len)));
		}
		while(size>1&&digits[size]==0)pop();
		return *this;
	}
	__intinf&__intinf::operator=(const vector<bool>&b){
		if(b[0]==0){
			*this=0;
			__intinf pw2=1;
			for(int i=b.size()-1;i>=1;i--,pw2+=pw2)if(b[i])*this+=pw2;
			return *this;
		}
		else{
			*this=0;
			__intinf pw2=1;
			for(int i=b.size()-1;i>=1;i--,pw2+=pw2)if(!b[i])*this-=pw2;
			*this-=1;
			return *this;
		}
	}
	void __intinf::clear(){if(digits!=nullptr)delete[] digits,digits=nullptr;}
	string __intinf::to_string()const{stringstream ss;ss<<*this;return ss.str();}
	long long __intinf::to_long_long()const{return stoll(to_string());}
	vector<bool>__intinf::to_binary()const{
		if(*this==0)return{0};
		vector<bool>res;__intinf x;
		if(this->flag==true)x=*this;
		if(this->flag==false)x=~*this;
		for(;x!=0;x=x.div2())
			res.emplace_back(this->flag==true?x.digits[1]&1:!(x.digits[1]&1));
		if(this->flag==true)res.emplace_back(0);
		else res.emplace_back(1);
		reverse(res.begin(),res.end());
		return res;
	}
	__intinf __intinf::operator-()const{
		if(*this==0)return 0;
		__intinf res=*this;res.flag=!flag;return res;
	}
	__intinf __intinf::operator~()const{return -(*this)-1;}
	__intinf __intinf::abs()const{__intinf res=*this;res.flag=true;return res;}
	__intinf __intinf::abs(const __intinf&a){return a.abs();}
	int __intinf::_digit_len()const{return size;}
	bool __intinf::operator==(const __intinf&x)const{return compare(x)==0;}
	#if __cplusplus >= 202002L
	auto __intinf::operator<=>(const __intinf&x)const{return compare(x);}
	#else
	bool __intinf::operator<(const __intinf&x)const{return compare(x)<0;}
	bool __intinf::operator>(const __intinf&x)const{return compare(x)>0;}
	bool __intinf::operator!=(const __intinf&x)const{return compare(x)!=0;}
	bool __intinf::operator<=(const __intinf&x)const{return compare(x)<=0;}
	bool __intinf::operator>=(const __intinf&x)const{return compare(x)>=0;}
	#endif
	__intinf __intinf::operator+(const __intinf&x)const{
		if(!x.flag)return *this-x.abs();
		if(!flag)return x-abs();
		__intinf res; 
		res.flag=!(flag^x.flag);
		int n=max(size,x.size)+1;
		res.reserve(n);
		digit_t carry=0;
		for(int i=1;i<=n;i++){
			digit_t d1=i<=size?digits[i]:0,d2=i<=x.size?x.digits[i]:0;
			res.push(d1+d2+carry);
			carry=res.digits[i]/BASE;
			res.digits[i]%=BASE;
		}
		while(res.size>1&&res.digits[res.size]==0)res.pop();
		return res;
	}
	__intinf __intinf::operator-(const __intinf&x)const{
		if(!x.flag)return *this+x.abs();
		if(!flag)return -(abs()+x);
		__intinf res;
		if(*this<x)res.flag=false;
		digit_t carry=0;
		int n=max(size,x.size);
		res.reserve(n);
		for(int i=1;i<=n;i++){
			digit_t d1=i<=size?digits[i]:0,d2=i<=x.size?x.digits[i]:0;
			if(res.flag)res.push(d1-d2-carry);
			else res.push(d2-d1-carry);
			if(res.digits[i]<0)res.digits[i]+=BASE,carry=1;
			else carry=0;
		}
		while(res.size>1&&res.digits[res.size]==0)res.pop();
		return res;
	}
	namespace __FFT{
		constexpr long long FFT_BASE=1e4;
		constexpr double PI2=6.283185307179586231995927;
		constexpr double PI6=18.84955592153875869598778;
		constexpr int RECALC_WIDTH=10;
		constexpr int RECALC_BASE=(1<<RECALC_WIDTH)-1;
		struct complex{
			double real,imag;
			complex(double x=0.0,double y=0.0):real(x),imag(y){}
			complex operator+(const complex&other)const{return complex(real+other.real,imag+other.imag);}
			complex operator-(const complex&other)const{return complex(real-other.real,imag-other.imag);}
			complex operator*(const complex&other)const{return complex(real*other.real-imag*other.imag,real*other.imag+other.real*imag);}
			complex&operator+=(const complex&other){return real+=other.real,imag+=other.imag,*this;}
			complex&operator-=(const complex&other){return real-=other.real,imag-=other.imag,*this;}
			complex&operator*=(const complex&other){return *this=*this*other;}
		};
		complex* arr=nullptr;
		inline void init(int n){
			if(arr!=nullptr)delete[] arr,arr=nullptr;
			arr=new complex[n+1];
		}
		template<const int n>inline void fft(complex* a){
			const int n2=n>>1,n4=n>>2;
			complex w(1.0,0.0),w3(1.0,0.0);
			const complex wn(cos(PI2/n),sin(PI2/n)),wn3(cos(PI6/n),sin(PI6/n));
			for(int i=0;i<n4;i++,w*=wn,w3*=wn3){
				if(!(i&RECALC_BASE))w=complex(cos(PI2*i/n),sin(PI2*i/n)),w3=w*w*w;
				complex x=a[i]-a[i+n2],y=a[i+n4]-a[i+n2+n4];
				y=complex(y.imag,-y.real);
				a[i]+=a[i+n2],a[i+n4]+=a[i+n2+n4];
				a[i+n2]=(x-y)*w,a[i+n2+n4]=(x+y)*w3;
			}
			fft<n2>(a),fft<n4>(a+n2),fft<n4>(a+n2+n4);
		}
		template<>inline void fft<0>(complex*){}
		template<>inline void fft<1>(complex*){}
		template<>inline void fft<2>(complex* a){
			complex x=a[0],y=a[1];
			a[0]+=y,a[1]=x-y;
		}
		template<>inline void fft<4>(complex* a){
			complex a0=a[0],a1=a[1],a2=a[2],a3=a[3];
			complex x=a0-a2,y=a1-a3;
			y=complex(y.imag,-y.real);
			a[0]+=a2,a[1]+=a3,a[2]=x-y,a[3]=x+y;
			fft<2>(a);
		}
		template<const int n>inline void ifft(complex* a){
			const int n2=n>>1,n4=n>>2;
			ifft<n2>(a),ifft<n4>(a+n2),ifft<n4>(a+n2+n4);
			complex w(1.0,0.0),w3(1.0,0.0);
			const complex wn(cos(PI2/n),-sin(PI2/n)),wn3(cos(PI6/n),-sin(PI6/n));
			for(int i=0;i<n4;i++,w*=wn,w3*=wn3){
				if(!(i&RECALC_BASE))w=complex(cos(PI2*i/n),-sin(PI2*i/n)),w3=w*w*w;
				complex p=w*a[i+n2],q=w3*a[i+n2+n4];
				complex x=a[i],y=p+q,x1=a[i+n4],y1=p-q;
				y1=complex(y1.imag,-y1.real);
				a[i]+=y,a[i+n4]+=y1,a[i+n2]=x-y,a[i+n2+n4]=x1-y1;
			}
		}
		template<>inline void ifft<0>(complex*){}
		template<>inline void ifft<1>(complex*){}
		template<>inline void ifft<2>(complex* a){
			complex x=a[0],y=a[1];
			a[0]+=y,a[1]=x-y;
		}
		template<>inline void ifft<4>(complex* a){
			ifft<2>(a);
			complex p=a[2],q=a[3];
			complex x=a[0],y=p+q,x1=a[1],y1=p-q;
			y1=complex(y1.imag,-y1.real);
			a[0]+=y,a[1]+=y1,a[2]=x-y,a[3]=x1-y1;
		}
		inline void dft(complex* a,int n){
			if(n<=1)return;
			switch(n){
				case 1<<2:fft<1<<2>(a);break;
				case 1<<3:fft<1<<3>(a);break;
				case 1<<4:fft<1<<4>(a);break;
				case 1<<5:fft<1<<5>(a);break;
				case 1<<6:fft<1<<6>(a);break;
				case 1<<7:fft<1<<7>(a);break;
				case 1<<8:fft<1<<8>(a);break;
				case 1<<9:fft<1<<9>(a);break;
				case 1<<10:fft<1<<10>(a);break;
				case 1<<11:fft<1<<11>(a);break;
				case 1<<12:fft<1<<12>(a);break;
				case 1<<13:fft<1<<13>(a);break;
				case 1<<14:fft<1<<14>(a);break;
				case 1<<15:fft<1<<15>(a);break;
				case 1<<16:fft<1<<16>(a);break;
				case 1<<17:fft<1<<17>(a);break;
				case 1<<18:fft<1<<18>(a);break;
				case 1<<19:fft<1<<19>(a);break;
				case 1<<20:fft<1<<20>(a);break;
				case 1<<21:fft<1<<21>(a);break;
				case 1<<22:fft<1<<22>(a);break;
				case 1<<23:fft<1<<23>(a);break;
				case 1<<24:fft<1<<24>(a);break;
				case 1<<25:fft<1<<25>(a);break;
				case 1<<26:fft<1<<26>(a);break;
				case 1<<27:fft<1<<27>(a);break;
				case 1<<28:fft<1<<28>(a);break;
				case 1<<29:fft<1<<29>(a);break;
				case 1<<30:fft<1<<30>(a);break;
				throw FFTLimitExceededError();
			}
		}
		inline void idft(complex* a,int n){
			if(n<=1)return;
			switch(n){
				case 1<<2:ifft<1<<2>(a);break;
				case 1<<3:ifft<1<<3>(a);break;
				case 1<<4:ifft<1<<4>(a);break;
				case 1<<5:ifft<1<<5>(a);break;
				case 1<<6:ifft<1<<6>(a);break;
				case 1<<7:ifft<1<<7>(a);break;
				case 1<<8:ifft<1<<8>(a);break;
				case 1<<9:ifft<1<<9>(a);break;
				case 1<<10:ifft<1<<10>(a);break;
				case 1<<11:ifft<1<<11>(a);break;
				case 1<<12:ifft<1<<12>(a);break;
				case 1<<13:ifft<1<<13>(a);break;
				case 1<<14:ifft<1<<14>(a);break;
				case 1<<15:ifft<1<<15>(a);break;
				case 1<<16:ifft<1<<16>(a);break;
				case 1<<17:ifft<1<<17>(a);break;
				case 1<<18:ifft<1<<18>(a);break;
				case 1<<19:ifft<1<<19>(a);break;
				case 1<<20:ifft<1<<20>(a);break;
				case 1<<21:ifft<1<<21>(a);break;
				case 1<<22:ifft<1<<22>(a);break;
				case 1<<23:ifft<1<<23>(a);break;
				case 1<<24:ifft<1<<24>(a);break;
				case 1<<25:ifft<1<<25>(a);break;
				case 1<<26:ifft<1<<26>(a);break;
				case 1<<27:ifft<1<<27>(a);break;
				case 1<<28:ifft<1<<28>(a);break;
				case 1<<29:ifft<1<<29>(a);break;
				case 1<<30:ifft<1<<30>(a);break;
				throw FFTLimitExceededError();
			}
		}
	}
	__intinf __intinf::fft_mul(const __intinf&a,const __intinf&b){
		int least=(a.size+b.size)<<1,lim=1<<__lg(least);
		if(lim<least)lim<<=1;
		__FFT::init(lim);
		using __FFT::arr;
		for(int i=0;i<a.size;i++){
			arr[i<<1].real=a.digits[i+1]%10000;
			arr[i<<1|1].real=a.digits[i+1]/10000%10000;
		}
		for(int i=0;i<b.size;i++){
			arr[i<<1].imag=b.digits[i+1]%10000;
			arr[i<<1|1].imag=b.digits[i+1]/10000%10000;
		}
		__FFT::dft(arr,lim);
		for(int i=0;i<lim;i++)arr[i]*=arr[i];
		__FFT::idft(arr,lim);
		__intinf res;
		res.resize(a.size+b.size+1);
		digit_t carry=0;
		double inv=0.5/lim;
		for(int i=0;i<=a.size+b.size;i++){
			carry+=(digit_t)(arr[i<<1].imag*inv+0.5);
			carry+=(digit_t)(arr[i<<1|1].imag*inv+0.5)*10000LL;
			res.digits[i+1]+=carry%BASE,carry/=BASE;
		}
		while(res.size>1&&res.digits[res.size]==0)res.pop();
		return res;
	}
	__intinf __intinf::operator*(const __intinf&x)const{
		__intinf zero=0;
		if(*this==zero||x==zero)return zero;
		int n=size,m=x.size;
		if(1LL*n*m>=FFT_LIMIT){
			__intinf res=fft_mul(*this,x);
			res.flag=!(flag^x.flag);
			return res;
		}
		__intinf res;
		res.flag=!(flag^x.flag);
		res.resize(n+m+2);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				res.digits[i+j-1]+=digits[i]*x.digits[j];
				res.digits[i+j]+=res.digits[i+j-1]/BASE;
				res.digits[i+j-1]%=BASE;
			}
		for(int i=1;i<=n+m+1;i++){
			res.digits[i+1]+=res.digits[i]/BASE;
			res.digits[i]%=BASE;
		}
		while(res.size>1&&res.digits[res.size]==0)res.pop();
		return res;
	}
	__intinf&__intinf::operator*=(int x){
		if(x==0||*this==0)return *this=0;
		if(x<0)flag=!flag,x=-x;
		digit_t carry=0;
		for(int i=1;i<=size||carry;i++){
			if(i>size)push(0);
			digit_t cur=digits[i]*x+carry;
			carry=cur/__intinf::BASE;
			digits[i]=cur%__intinf::BASE;
		}
		while(size>1&&digits[size]==0)pop();
		return *this;
	}
	__intinf __intinf::operator*(const int&x)const{__intinf t=*this;return t*=x;}
	__intinf __intinf::div2()const{
		__intinf res=*this;
		for(int i=size;i>=1;i--){
			if((res.digits[i]&1)&&(i>1))res.digits[i-1]+=BASE;
			res.digits[i]>>=1;
		}
		while (res.size>1&&res.digits[res.size]==0)res.pop();
		return res;
	}
	__intinf __intinf::operator/(const long long&x)const{
		if(x==0)throw -1;
		if(*this==0)return 0;
		if(x==2)return div2();
		if(x==-2){__intinf res=div2();res.flag=!res.flag;return res;}
		__intinf res;
		res.flag=!(flag^(x>=0));
		digit_t cur=0,div=std::abs(x);
		res.resize(size);
		for(int i=size;i>=1;i--){
			cur=cur*BASE+digits[i];
			res.digits[i]=res.flag?(cur/div):(-cur/-div);
			cur%=div;
		}
		while(res.size>1&&res.digits[res.size]==0)res.pop();
		return res;
	}
	inline __intinf __intinf::_move_r(int d)const{
		if(*this==0||d>=size)return 0;
		if(d==0)return *this;
		__intinf res;res.reserve(size-d+1);
		for(int i=d+1;i<=size;i++)res.push(digits[i]);
		return res;
	}
	inline __intinf __intinf::_move_l(int d)const{
		if(*this==0)return 0;
		if(d==0)return *this;
		__intinf res;res.reserve(size+d+1);
		for(int i=1;i<=d;i++)res.push(0);
		for(int i=1;i<=size;i++)res.push(digits[i]);
		return res;
	}
	__intinf __intinf::newton_inv(int n)const{
		if(*this==0)throw ZeroDivisionError();
		if(min(size,n-size)<=NEWTON_MIN_LEVEL){
			__intinf a;a.resize(n+1);
			memset(a.digits,0,sizeof(digit_t)*a.size);
			a.digits[n+1]=1;
			return a.divmod(*this,true).first;
		}
		int k=(n-size+2)>>1,k2=k>size?0:size-k;
		__intinf x=_move_r(k2);
		int n2=k+x.size;
		__intinf y=x.newton_inv(n2),a=y+y,b=(*this)*y*y;
		return a._move_l(n-n2-k2)-b._move_r(2*(n2+k2)-n)-1;
	}
	pair<__intinf,__intinf>__intinf::newton_div(const __intinf&x)const{
		int k=size-x.size+2,k2=k>x.size?0:x.size-k;
		__intinf x2=x._move_r(k2);
		if(k2!=0)x2+=1;
		int n2=k+x2.size;
		__intinf u=(*this)*x2.newton_inv(n2);
		__intinf q=u._move_r(n2+k2),r=(*this)-q*x;
		while(r>=x)q+=1,r-=x;
		return make_pair(q,r);
	}
	pair<__intinf,__intinf>__intinf::divmod(const __intinf&x,bool dis_newton)const{
		static const int base=__intinf::BASE;
		__intinf a=abs(),b=x.abs();
		if(b==0)throw ZeroDivisionError();
		if(a<b)return make_pair(0,flag?a:-a);
		if(!dis_newton&&size>NEWTON_LIMIT)return newton_div(x);
		int t=base/(x.digits[x.size]+1);
		a*=t,b*=t;
		int n=a.size,m=b.size;
		__intinf q=0,r=0;
		q.resize(n);
		for(int i=n;i>=1;i--){
			r*=base,r+=a.digits[i];
			digit_t d1=m<r.size?r.digits[m+1]:0,d2=m-1<r.size?r.digits[m]:0;
			int d=(d1*base+d2)/b.digits[m];
			r-=b*d;
			while(!r.flag)r+=b,d--;
			q.digits[i]=d;
		}
		q.flag=!(flag^x.flag),r.flag=flag;
		while(q.size>1&&q.digits[q.size]==0)q.pop();
		return make_pair(q,r/t);
	}
	__intinf __intinf::operator/(const __intinf&x)const{return divmod(x).first;}
	__intinf __intinf::operator%(const long long&x)const{
		if(x==2||x==4||x==5)return digits[1]%x;
		return *this-(*this/x*x);
	}
	__intinf __intinf::operator%(const __intinf&x)const{return divmod(x).second;}
	__intinf __intinf::pow(const long long&x)const{
		__intinf res=1,a=*this;
		for(long long t=x;t!=0;a*=a,t>>=1)if(t&1)res*=a;
		return res;
	}
	__intinf __intinf::pow(const long long&x,const __intinf&p)const{
		__intinf res=1,a=*this%p;
		for(long long t=x;t!=0;a=a*a%p,t>>=1)if(t&1)res=res*a%p;
		return res;
	}
	__intinf __intinf::root(const long long&m)const{
		if(*this==0||m==1)return *this;
		if(m==2)return sqrt();
		static constexpr long long base=__intinf::BASE;
		__intinf n=*this,t=base,x0=min(n,t._move_l((n.size+m)/m));
		long long l=0,r=base-1;
		while(l<r){
			long long mid=(l+r)>>1;
			x0.digits[x0.size]=mid;
			if(x0.pow(m)<=n)l=mid+1;
			else r=mid;
		}
		x0.digits[x0.size]=l;
		while(x0.size>1&& x0.digits[x0.size]==0)x0.pop();
		__intinf x=(x0*(m-1)+n/x0.pow(m-1))/m;
		while(x<x0)swap(x,x0),x=(x0*(m-1)+n/x0.pow(m-1))/m;
		return x0;
	}
	__intinf __intinf::sqrt()const{
		if(*this<=1)return *this;
		static constexpr long long base=__intinf::BASE;
		__intinf n=*this,x0=__intinf(base)._move_l((n.size+2)>>1);
		__intinf x=(x0+n/x0).div2();
		while (x<x0)swap(x,x0),x=(x0+n/x0).div2();
		return x0;
	}
	__intinf __intinf::gcd(const __intinf&x)const{
		__intinf a=*this,b=x;
		if(a<b)swap(a,b);
		if(b==0)return a;
		int t=0;
		while(a%2==0&&b%2==0)a=a.div2(),b=b.div2(),t++;
		while(b>0){
			if(a%2==0)a=a.div2();
			else if(b%2==0)b=b.div2();
			else a-=b;
			if(a<b)swap(a,b);
		}
		while(t--)a+=a;
		return a;
	}
	__intinf __intinf::lcm(const __intinf& x)const{return *this/gcd(x)*x;}
	__intinf __intinf::pow(const __intinf&a,const long long&b){return a.pow(b);}
	__intinf __intinf::pow(const __intinf&a,const long long&b,const __intinf&c){return a.pow(b,c);}
	__intinf __intinf::root(const __intinf&a,const long long&b){return a.root(b);}
	__intinf __intinf::sqrt(const __intinf&a){return a.sqrt();}
	__intinf __intinf::gcd(const __intinf&a,const __intinf&b){return a.gcd(b);}
	__intinf __intinf::lcm(const __intinf&a,const __intinf&b){return a.lcm(b);}
	__intinf&__intinf::operator+=(const __intinf&x){return *this=*this+x;}
	__intinf&__intinf::operator-=(const __intinf&x){return *this=*this-x;}
	__intinf&__intinf::operator*=(const __intinf&x){return *this=*this*x;}
	__intinf&__intinf::operator/=(const long long&x){return *this=*this/x;}
	__intinf&__intinf::operator/=(const __intinf&x){return *this=*this/x;}
	__intinf&__intinf::operator%=(const long long&x){return *this=*this/x;}
	__intinf&__intinf::operator%=(const __intinf&x){return *this=*this%x;}
	__intinf __intinf::operator<<(const long long&x){
		if(x<=0)return *this;
		__intinf res=*this;
		for(long long i=1;i<=x;i++)res+=res;
		return res;
	}
	__intinf __intinf::operator>>(const long long&x){
		if(x<=0)return *this;
		__intinf res=*this;
		for(long long i=1;i<=x;i++)res=res.div2();
		return res;
	}
	__intinf&__intinf::operator<<=(const long long&x){return *this=*this<<x;}
	__intinf&__intinf::operator>>=(const long long&x){return *this=*this>>x;}
	template<class F>inline __intinf __intinf::binary_op_helper(const __intinf&x,const __intinf&y,const F&func){
		auto to_bin=[](__intinf x,int n)->vector<bool>{
			if(x==0)return{0};
			vector<bool>res;
			__intinf t;
			if(x>0)t=x;
			else t=~x;
			for(;t!=0;t=t.div2())
				res.emplace_back(x>0?t.digits[1]&1:!(t.digits[1]&1));
			while(res.size()<n)
				if(x>0)res.emplace_back(0);
				else res.emplace_back(1);
			reverse(res.begin(),res.end());
			return res;
		};
		__intinf u=x,v=y;
		if(u.abs()<v.abs())swap(u,v);
		vector<bool>a=u.to_binary();
		int n=a.size();
		vector<bool>b=to_bin(v,n);
		vector<bool>res(n,0);
		for(int i=n-1;i>=0;i--)res[i]=func(a[i],b[i]);
		return res;
	}
	__intinf __intinf::operator&(const __intinf&x){return binary_op_helper(*this,x,[](bool a,bool b)->bool{return a&b;});}
	__intinf __intinf::operator|(const __intinf&x){return binary_op_helper(*this,x,[](bool a,bool b)->bool{return a|b;});}
	__intinf __intinf::operator^(const __intinf&x){return binary_op_helper(*this,x,[](bool a,bool b)->bool{return a^b;});}
	__intinf&__intinf::operator&=(const __intinf&x){return *this=*this&x;}
	__intinf&__intinf::operator|=(const __intinf&x){return *this=*this|x;}
	__intinf&__intinf::operator^=(const __intinf&x){return *this=*this^x;}
	__intinf&__intinf::operator++(){return *this+=1;}
	__intinf __intinf::operator++(int){__intinf t=*this;return *this+=1,t;}
	__intinf&__intinf::operator--(){return *this-=1;}
	__intinf __intinf::operator--(int){__intinf t=*this;return *this-=1,t;}
}