高精度头文件

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define ps __gnu_pbds
#define tree ps::tree<pair<int,int>,ps::null_type,less<pair<int,int> >,ps::rb_tree_tag,ps::tree_order_statistics_node_update>
namespace high_precision{
	string s1,s2;
	const int PREABMX=5005,PRECMX=25000005;
	int a[PREABMX]={0},b[PREABMX]={0},c[PRECMX]={0},resn=0,isf=0;
	void init_a(){
		for(int i=s1.length()-1;i>=0;i--){
			int k=s1.length()-i;
			a[k]=s1[i]-'0';
		}
		return;
	}
	void init_b(){
		for(int i=s2.length()-1;i>=0;i--){
			int k=s2.length()-i;
			b[k]=s2[i]-'0';
		}
		return;
	}
	void addition(){
		isf=0;
		int mxn=max(s1.length(),s2.length()),jin=0;
		for(int i=1;i<=mxn;i++){
			c[i]=a[i]+b[i]+jin;
			jin=0;
			if(c[i]>=10) c[i]-=10,jin=1;
		}
		if(jin) resn=mxn+1,c[resn]=1;
		else resn=mxn;
	}
	void multiplication(){
		int lena=s1.length();
		int lenb=s2.length();
		resn=0,isf=0;
		for(int i=1;i<=lenb;i++){
			int jin=0;
			for(int j=1;j<=lena;j++){
				resn=max(resn,i+j-1);
				c[i+j-1]+=b[i]*a[j]+jin;
				jin=0;
				if(c[i+j-1]>=10) jin=c[i+j-1]/10,c[i+j-1]%=10;
			}
			if(jin) c[lena+i]=jin,resn=max(resn,(int)(lena+i));
		}
	}
	void subtraction(){
		resn=0,isf=0;
		int mxn=max(s1.length(),s2.length()),jin=0;
		for(int i=mxn;i>=1;i--){
			if(a[i]<b[i]){
				swap(a,b);
				isf=1;
				break;
			}else if(a[i]>b[i]){
				break;
			} 
		}
		for(int i=1;i<=mxn;i++){
			c[i]=a[i]-b[i]-jin;
			jin=0;
			if(c[i]<0){
				c[i]+=10;
				jin=1;
			}
		}
		resn=mxn;
	}
	void division_int(long long x){
		long long yu=0;
		for(int i=s1.length();i>=1;i--){
			yu=yu*10+a[i];
			c[i]=yu/x;
			yu=yu%x;
		}
		resn=s1.length();
	}
	void high_min(){
		int lena=s1.length();
		int lenb=s2.length();
		int k=1;
		for(int i=max(lena,lenb);i>=1;i--){
			if(a[i]>b[i]){
				k=2;
				break;
			}else if(a[i]<b[i]){
				break;
			}
		}
		if(k==1){
			for(int i=lena;i>=1;i--){
				c[i]=a[i];
			}
			resn=lena;
		}else{
			for(int i=lenb;i>=1;i--){
				c[i]=b[i];
			}
			resn=lenb;
		}
	}
	void high_max(){
		int lena=s1.length();
		int lenb=s2.length();
		int k=1;
		for(int i=max(lena,lenb);i>=1;i--){
			if(a[i]>b[i]){
				break;
			}else if(a[i]<b[i]){
				k=2;
				break;
			}
		}
		if(k==1){
			for(int i=lena;i>=1;i--){
				c[i]=a[i];
			}
			resn=lena;
		}else{
			for(int i=lenb;i>=1;i--){
				c[i]=b[i];
			}
			resn=lenb;
		}
	}
	void print(){
		if(isf) printf("-"),isf=0; 
		int k=resn;
		while(c[k]==0&&k>1) k--;
		for(int i=k;i>=1;i--){
			printf("%d",c[i]);
		}
	}
	int fstring(long long x){
		int k=0;
		while(x){
			b[++k]=x%10;
			x/=10;
		}
		return k;
	}
}
using namespace high_precision;