//====================================================================
// One of @C24zhengfujia's program
// Copyright (C) 2024 C24zhengfujia, All rights reserved.

// This file is posted on zxoj.net.

// This code is distributed in the hope that it will be useful,
// but DO NOT COPY ANYTHING; if you've been punished or been 
// kicked out because you copied something. No people but YOU have to handle this issue.
// See zxoj.net or visit Ms He for more details.

/*
 * This is one of @C24zhengfujia's program.
 */

//
// zxoj.net/d/ybtqm/blog/201/6707be64f2e492a8081ed04c#1728560740345  #BIGINT,2024-12-6
//

//Signature:C24zhengfujia
//====================================================================

//====================================================================
// @C24zhengfujia的作品之一
// 版权所有（C）2024 C24zhengfujia，保留所有权利。

// 此文件发布在zxoj.net上。

// 分发此代码是希望它有用，
// 但不要复制任何东西；如果你受到了惩罚或
// 被开除是因为你抄袭了一些东西。除了你，没有人必须处理这个问题。
// 请访问zxoj.net或找何老师以获取更多详细信息。

/*
* 这是@C24zhengfujia的作品之一。
*/

//
// zxoj.net/d/ybtqm/blog/201/6707be64f2e492a8081ed04c#1728560740345 #BIGINT，2024-12-6
//

// 签字：C24zhengfujia
//====================================================================
#include<istream>
#include<ostream>
#include<string>

namespace std 
{
	struct bigint{
		basic_string<int> num;
		bool minus;
		
		bigint operator = (long long n)
		{
			num.clear();
			if(n<0)
				n=-n,minus=true; 
			do{
				num.push_back(n%10);
				n/=10;
			}while(n);
			return *this;
		}
		
		bigint(long long n=0) {minus=false;*this=n;}
		
		inline int size() {return num.size();}
		
		inline void push_back(int n) {num.push_back(n);}
		
		int& operator [](int x)
		{
			return num[x];
		}
		
		void clear()
		{
			num.clear();
		}
	};
	
	istream& operator >> (istream &in,bigint &dest);
	ostream& operator << (ostream &out,bigint src);
	bool operator < (bigint a,bigint b);
	bool operator > (bigint a,bigint b);
	bool operator <= (bigint a,bigint b);
	bool operator >= (bigint a,bigint b);
	bool operator == (bigint a,bigint b);
	bool operator != (bigint a,bigint b);
	bigint operator + (bigint a,bigint b);
	bigint operator - (bigint a,bigint b);
	bigint operator * (bigint a,bigint b);
	bigint operator * (bigint a,int b);
	bigint operator / (bigint a,bigint b);
	bigint operator += (bigint a,bigint b);
	bigint operator -= (bigint a,bigint b);
//	bigint operator *= (bigint a,bigint b);
//	bigint operator *= (bigint a,int b);
	bigint operator /= (bigint a,bigint b);
	
	istream& operator >> (istream &in,bigint &dest)
	{
		string s;
		in>>s;
		if(s[0]=='-')
			s=s.erase(0,1);
		dest.clear();
		for(int i=s.length()-1;i>=0;--i)
			dest.push_back(s[i]-'0');
		return in;
	}
	
	ostream& operator << (ostream &out,bigint src)
	{
		if(src.minus)
			out<<'-';
		bool flag=false;
		for(int i=src.size();i>=0;--i)
		{
			if(src[i]) flag=true;
			if(flag) out<<src[i];
		}
		return out;
	}
	
	bool operator < (bigint a,bigint b)
	{
		if(a.size()!=b.size()) return a.size()<b.size();
		for(int i=0;i<a.size();++i)
			if(a[i]!=b[i])
				return a[i]<b[i];
		return false;
	}
	
	bool operator > (bigint a,bigint b)
	{
		if(a.size()!=b.size()) return a.size()>b.size();
		for(int i=0;i<a.size();++i)
			if(a[i]!=b[i])
				return a[i]>b[i];
		return false;
	}
	
	bool operator == (bigint a,bigint b)
	{
		if(a.size()!=b.size()) return false;
		for(int i=0;i<a.size();++i)
			if(a[i]!=b[i])
				return false;
		return true;
	}
	
	bool operator != (bigint a,bigint b)
	{
		return !(a==b);
	}
	
	bool operator >= (bigint a,bigint b)
	{
		if(a.size()!=b.size()) return a.size()>b.size();
		for(int i=0;i<a.size();++i)
			if(a[i]!=b[i])
				return a[i]>b[i];
		return true;
	}
	
	bool operator <= (bigint a,bigint b)
	{
		if(a.size()!=b.size()) return a.size()<b.size();
		for(int i=0;i<a.size();++i)
			if(a[i]!=b[i])
				return a[i]<b[i];
		return true;
	}
	
	bigint operator + (bigint a,bigint b)
	{
		int temp=0;
		bigint sum;
		sum.clear();
		for(int i=0;i<a.size()||i<b.size();++i)
		{
			if(i<a.size())temp+=a[i];
			if(i<b.size())temp+=b[i];
			sum.push_back(temp%10);
			temp/=10;
		}
		if(temp) sum.push_back(temp);
		return sum;
	}
	
	bigint operator - (bigint a,bigint b)
	{
		int temp=0;
		bigint sum;
		if(a<b)
		{
			swap(a,b);
			sum.minus=true;
		}
		sum.clear();
		for(int i=0;i<a.size();++i)
		{
			temp+=a[i];
			if(i<b.size()) temp-=b[i];
			sum.push_back((temp+10)%10);
			if(temp<0) temp=-1;
			else temp=0;
		}
		return sum;
	}
	
	bigint operator * (bigint a,bigint b)
	{
		basic_string<int> c(a.size()+b.size(),0);
		bigint sum;
		for(int i=0;i<a.size();++i)
			for(int j=0;j<b.size();++j)
			{
				c[i+j]+=a[i]*b[j];
				c[i+j+1]+=c[i+j]/10;
				c[i+j]%=10;
			}
		sum.num=c;
		return sum;
	}
	
	bigint operator * (bigint a,int b)
	{
		basic_string<int> c(a.size()+11,0);
		bigint sum;
		for(int i=0;i<a.size();++i)
			{
				c[i]+=a[i]*b;
				c[i+1]+=c[i]/10;
				c[i]%=10;
			}
		sum.num=c;
		return sum;
	}
	
	//bigint operator / (bigint a,bigint b)
	//{
	//	cout<<"Not Available!"<<endl;
	//	bigint c;
	//	return c;
	//}
	
	//bigint operator % (bigint a,bigint b)
	//{
	//	cout<<"Not Available!"<<endl;
	//	bigint c;
	//	return c;
	//}
	
	bigint operator += (bigint &a,bigint b)
	{
		return a=a+b;
	}
	
	bigint operator -= (bigint &a,bigint b)
	{
		return a=a-b;
	}
	
	bigint operator *= (bigint &a,bigint b)
	{
		return a=a*b;
	}
	
	bigint operator *= (bigint &a,int b)
	{
		return a=a*b;
	}
}