好用的代码

现在可以看了
run里面自己加自己想加的东西即可
终于写完了啊啊啊啊啊啊啊啊啊啊啊啊
不喜勿喷，代码里需要可以直接用，不用声明是我的。

#include<bits/stdc++.h>
using namespace std;
const unsigned long long ullmax=18446744073709551615ull;
const int mod=998244353;
const int g=3;
int base=10;
unsigned long long ullabs(long long a){
	if(a>=0) return (unsigned long long)a;
	unsigned long long res=(unsigned long long)a;
	res=ullmax-res+1;
	return res;
}
int powmod(long long a,long long b){
	long long res=1;
	while(b){
		if(b%2==1) res=res*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return (int)res;
}
int toint(char c){
	if('0'<=c&&c<='9') return c-'0';
	else return c-'A'+10;
}
char tochar(int a){
	if(0<=a&&a<=9) return a+'0';
	else return a+'A'-10;
}
string forms(const string& s){
	int i=s.size();
	for(;i>1&&s[i-1]=='0';i--);
	return s.substr(0,i);
}
bool ucmp(const string& a,const string& b){
	if(a.size()<b.size()) return true;
	if(a.size()>b.size()) return false;
	for(int i=(int)a.size()-1;i>=0;i--){
		if(a[i]>b[i]) return false;
		if(a[i]<b[i]) return true;
	}
	return false;
}
string usub(string a,string b){
	bool flag=false;
	string ans="";
	if(ucmp(a,b)){
		flag=true;
		swap(a,b);
	}
	int now=0;
	for(int i=0;i<(int)a.size();i++){
		int x;
		if(i<(int)b.size()) x=toint(b[i]);
		else x=0;
		if(toint(a[i])-now<x){
			ans+=tochar(toint(a[i])+base-now-x);
			now=1;
		}else{
			ans+=tochar(toint(a[i])-now-x);
			now=0;
		}
	}
	ans=forms(ans);
	if(flag) ans=ans+"-";
	return ans;
}
string uadd(const string& a,const string& b){
	string ans="";
	int nx=0,now=0,len=max(a.size(),b.size());
	for(int i=0;i<len;i++){
		nx=0;
		if(i<(int)a.size()) nx+=toint(a[i]);
		if(i<(int)b.size()) nx+=toint(b[i]);
		nx+=now;
		now=0;
		if(nx>=base){
			now=1;
			nx-=base;
		}
		ans+=tochar(nx);
	}
	ans+=tochar(now);
	return forms(ans);
}
void ntt(vector<int>& a,bool b){
	int n=a.size();
	vector<int>to(n,0);
	for(int i=0;i<n;i++){
		to[i]=to[i>>1]>>1;
		if(i&1) to[i]|=(n>>1);
		if(i<to[i]) swap(a[i],a[to[i]]);
	}
	for(int l=2;l<=n;l<<=1){
		int wl=powmod(g,(mod-1)/l);
		if(b) wl=powmod(wl,mod-2);
		for(int i=0;i<n;i+=l){
			long long w=1;
			int mid=l>>1;
			for(int j=0;j<mid;j++){
				int x=a[i+j],y=w*a[i+j+mid]%mod;
				a[i+j]=(1ll*x+y)%mod;
				a[i+j+mid]=(1ll*x-y+mod)%mod;
				w=w*wl%mod;
			}
		}
	}
	if(b){
		int nf=powmod(n,mod-2);
		for(int i=0;i<n;i++) a[i]=1ll*a[i]*nf%mod;
	}
}
string umul(const string& a,const string& b){
	vector<int>va,vb;
	for(int i=0;i<(int)a.size();i++) va.push_back(toint(a[i]));
	for(int i=0;i<(int)b.size();i++) vb.push_back(toint(b[i]));
	int n=1;
	while(n<(int)va.size()+(int)vb.size()-1) n<<=1;
	va.resize(n);
	vb.resize(n);
	ntt(va,false);
	ntt(vb,false);
	for(int i=0;i<(int)va.size();i++) va[i]=1ll*va[i]*vb[i]%mod;
	ntt(va,true);
	for(int i=0;i<(int)va.size();i++){
		if(i<(int)va.size()-1) va[i+1]+=va[i]/base;
		else if(va[i]/base>0) va.push_back(va[i]/base);
		va[i]%=base;
	}
	string ans;
	for(int i=0;i<(int)va.size();i++) ans+=tochar(va[i]);
	return forms(ans);
}
pair<string,string> udiv(const string& a,const string& b){
	if(b=="0") throw runtime_error("除以零");
	if(a=="0") return {"0","0"};
	string r="0";
	string hq="";
	string na[44];
	na[0]="0";
	for(int nq=1;nq<base;nq++) na[nq]=uadd(na[nq-1],b);
	for(int i=(int)a.size()-1;i>=0;i--){
		r="0"+r;
		r=uadd(r,string(1,a[i]));
		int nq=base-1;
		while(nq>=0){
			if(!ucmp(r,na[nq])){
				r=usub(r,na[nq]);
				break;
			}
			nq--;
		}
		hq+=tochar(nq);
	}
	string q=hq;
	reverse(q.begin(),q.end());
	return {forms(q),forms(r)};
}
string to_string_ll(long long a){
	string s;
	if(a==0) return "0";
	unsigned long long x=ullabs(a);
	while(x){
		s+=tochar(x%base);
		x/=base;
	}
	if(a<0) s+="-";
	return s;
}
class bnum{
private:
	bool pn;
	string num;
	void form(){
		num=forms(num);
		if((int)num.size()==1&&num[0]=='0') pn=true;
	}
public:
	bnum():pn(true),num("0"){}
	bnum(bool b,string s):pn(b),num(s){
		form();
	}
	bnum(string s){
		if(!s.size()){
			num="0";
			pn=true;
		}else{
			if(s[(int)s.size()-1]=='-'){
				num=s.substr(0,(int)s.size()-1);
				pn=false;
			}else if(s[(int)s.size()-1]=='+'){
				num=s.substr(0,(int)s.size()-1);
				pn=true;
			}else{
				num=s;
				pn=true;
			}
		}
		if((int)num.size()==0) num="0";
		form();
	}
	bnum(long long x):bnum(to_string_ll(x)){}
	bnum(int x):bnum((long long)x){}
	explicit operator bool() const{
		return num!="0";
	}
	string get_num() const{
		string ans=num;
		reverse(ans.begin(),ans.end());
		return ans;
	}
	bool get_porn() const{return pn;}
	bnum& operator=(const bnum& other)=default;
	bnum& operator+=(const bnum& a){
		if(pn==a.pn){
			num=uadd(a.num,num);
			return *this;
		}else{
			num=usub(num,a.num);
			if(num[(int)num.size()-1]=='-'){
				pn=!pn;
				num=num.substr(0,(int)num.size()-1);
			}
			form();
			return *this;
		}
	}
	bnum& operator-=(const bnum& a){
		if(pn!=a.pn){
			num=uadd(a.num,num);
			return *this;
		}else{
			num=usub(num,a.num);
			if(num[(int)num.size()-1]=='-'){
				pn=!pn;
				num=num.substr(0,(int)num.size()-1);
			}
			form();
			return *this;
		}
	}
	bnum& operator*=(const bnum& a){
		num=umul(num,a.num);
		pn=(pn==a.pn);
		form();
		return *this;
	}
	bnum& operator/=(const bnum& a){
		num=udiv(num,a.num).first;
		pn=(pn==a.pn);
		form();
		return *this;
	}
	bnum& operator%=(const bnum& a){
		num=udiv(num,a.num).second;
		form();
		return *this;
	}
	bnum& operator++(){
		*this+=bnum(1);
		return *this;
	}
	bnum operator++(int){
		bnum old=*this;
		++(*this);
		return old;
	}
	bnum& operator--(){
		*this-=bnum(1);
		return *this;
	}
	bnum operator--(int){
		bnum old=*this;
		--(*this);
		return old;
	}
	friend bool operator==(const bnum& a,const bnum& b){
		if(a.pn!=b.pn) return false;
		if(a.num.size()!=b.num.size()) return false;
		for(int i=0;i<(int)a.num.size();i++){
			if(a.num[i]!=b.num[i]) return false;
		}
		return true;
	}
	friend bool operator<(const bnum& a,const bnum& b){
		if(a.pn&&!b.pn) return false;
		if(!a.pn&&b.pn) return true;
		if(a.pn) return ucmp(a.num,b.num);
		else return ucmp(b.num,a.num);
	}
	friend bool operator>(const bnum& a,const bnum& b){
		if(a.pn&&!b.pn) return true;
		if(!a.pn&&b.pn) return false;
		if(a.pn) return ucmp(b.num,a.num);
		else return ucmp(a.num,b.num);
	}
	friend bool operator<=(const bnum& a,const bnum& b){
		return !(a>b);
	}
	friend bool operator>=(const bnum& a,const bnum& b){
		return !(a<b);
	}
	friend bnum operator+(const bnum& a,const bnum& b){
		string ans;
		bool s=a.pn;
		if(a.pn==b.pn) ans=uadd(a.num,b.num);
		else{
			ans=usub(a.num,b.num);
			if(ans[(int)ans.size()-1]=='-'){
				s=!s;
				ans=ans.substr(0,(int)ans.size()-1);
			}
		}
		return bnum(s,ans);
	}
	friend bnum operator-(const bnum& a,const bnum& b){
		string ans;
		bool s=a.pn;
		if(a.pn!=b.pn) ans=uadd(a.num,b.num);
		else{
			ans=usub(a.num,b.num);
			if(ans[(int)ans.size()-1]=='-'){
				s=!s;
				ans=ans.substr(0,(int)ans.size()-1);
			}
		}
		return bnum(s,ans);
	}
	friend bnum operator*(const bnum& a,const bnum& b){
		string ans=umul(a.num,b.num);
		bool s=(a.pn==b.pn);
		return bnum(s,ans);
	}
	friend bnum operator/(const bnum& a,const bnum& b){
		string ans=udiv(a.num,b.num).first;
		bool s=(a.pn==b.pn);
		return bnum(s,ans);
	}
	friend bnum operator%(const bnum& a,const bnum& b){
		string ans=udiv(a.num,b.num).second;
		bool s=a.pn;
		return bnum(s,ans);
	}
	friend bnum operator-(const bnum& a){
		return bnum(!a.pn,a.num);
	}
	friend ostream& operator<<(ostream& o,const bnum& x){
		if(!x.pn) o<<'-';
		for(int i=(int)x.num.size()-1;i>=0;i--) o<<x.num[i];
		return o;
	}
	friend istream& operator>>(istream& i,bnum& x){
		string s;
		i>>s;
		if(i.fail()) return i;
		for(int j=0;j<(int)s.size();j++){
			if(!(j==0&&(s[j]=='+'||s[j]=='-'))&&!(('0'<=s[j]&&s[j]<='0'+min(base-1,9))||('A'<=s[j]&&s[j]<='A'+base-11))){
				i.setstate(ios::failbit);
				return i;
			}
		}
		reverse(s.begin(),s.end());
		x=bnum(s);
		return i;
	}
};
bnum abs(bnum a){
	if(a<0) a=-a;
	return a;
}
bnum gcd(bnum a,bnum b){
	if(a<b) swap(a,b);
	return (b==0)?a:gcd(b,a%b);
}
class frac{
private:
	bnum num;
	bnum den;
	void form(){
		if(den==0) throw runtime_error("分母为零 或 除以零");
		if(den<0){
			num=-num;
			den=-den;
		}
		bnum g=gcd(abs(num),den);
		num/=g;
		den/=g;
	}
public:
	frac(bnum n=0,bnum d=1):num(n),den(d){
		form();
	}
	bnum get_num() const{return num;}
	bnum get_den() const{return den;}
	frac& operator=(const frac& other)=default;
	frac& operator+=(const frac& f){
		num=num*f.den+f.num*den;
		den=den*f.den;
		form();
		return *this;
	}
	frac& operator-=(const frac& f){
		num=num*f.den-f.num*den;
		den=den*f.den;
		form();
		return *this;
	}
	frac& operator*=(const frac& f){
		num*=f.num;
		den*=f.den;
		form();
		return *this;
	}
	frac& operator/=(const frac& f){
		num*=f.den;
		den*=f.num;
		form();
		return *this;
	}
	friend frac operator+(const frac& a,const frac& b){
		return frac(a.num*b.den+b.num*a.den,a.den*b.den);		
	}
	friend frac operator-(const frac& a,const frac& b){
		return frac(a.num*b.den-b.num*a.den,a.den*b.den);		
	}
	friend frac operator*(const frac& a,const frac& b){
		return frac(a.num*b.num,a.den*b.den);		
	}
	friend frac operator/(const frac& a,const frac& b){
		return frac(a.num*b.den,a.den*b.num);		
	}
	friend frac operator-(const frac& a){
		return frac(-a.num,a.den);
	}
	friend bool operator==(const frac& a,const frac& b){
		 if(a.num==b.num&&a.den==b.den) return true;
		 return false;
	}
	friend bool operator<(const frac& a,const frac& b){
		if(a.num*b.den<b.num*a.den) return true;
		return false;
	}
	friend bool operator>(const frac& a,const frac& b){
		if(a.num*b.den>b.num*a.den) return true;
		return false;
	}
	friend bool operator<=(const frac& a,const frac& b){
		return (a<b)||(a==b);
	}
	friend bool operator>=(const frac& a,const frac& b){
		return (a>b)||(a==b);
	}
	friend ostream& operator<<(ostream& o,const frac& f){
		if(f.den==1) o<<f.num;
		else o<<f.num<<'/'<<f.den;
		return o;
	}
	friend istream& operator>>(istream& i,frac& f){
		bnum n,d=1;
		char s=0;
		if(!(i>>n)) return i;
		if(i.peek()=='/'){
			i>>s;
			if(!(i>>d)) return i;
		}
		if(d==0){
			i.setstate(ios::failbit);
			return i;
		}
		f=frac(n,d);
		return i;
	}
};
bool check_in(bool b){
	if(b){
		cout<<"请重新输入\n";
		cin.clear();
		cin.ignore(numeric_limits<streamsize>::max(),'\n');
	}
	return b;
}
void run(){
	frac f1,f2;
	do{
		cout<<"f1=";
		cin>>f1;
	}while(check_in(cin.fail()));
	do{
		cout<<"f2=";
		cin>>f2;
	}while(check_in(cin.fail()));
	cout<<"f1+f2="<<f1+f2<<endl;
	cout<<"f1-f2="<<f1-f2<<endl;
	cout<<"f1*f2="<<f1*f2<<endl;
	cout<<"f1/f2="<<f1/f2<<endl;
	if(f1>f2) cout<<"f1>f2"<<endl;
	if(f1<f2) cout<<"f1<f2"<<endl;
	if(f1==f2) cout<<"f1=f2"<<endl;
	if(f1>=f2) cout<<"f1>=f2"<<endl;
	if(f1<=f2) cout<<"f1<=f2"<<endl;
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("user.out","w",stdout);
	try{
		run();
	}catch(const runtime_error& e){
		cerr<<"错误："<<e.what()<<endl;
	}
	return 0;
}

--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
然后这个是头文件版：

#ifndef _more_nums_h
#define _more_nums_h
#include<string>
#include<vector>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<stdexcept>
#include<utility>
#include<cctype>
namespace mnums{
	const unsigned long long ullmax=18446744073709551615ull;
	const int mod=998244353;
	const int g=3;
	extern int base;
	inline unsigned long long ullabs(long long a){
		if(a>=0) return (unsigned long long)a;
		unsigned long long res=(unsigned long long)a;
		res=ullmax-res+1;
		return res;
	}
	inline int powmod(long long a,long long b){
		long long res=1;
		while(b){
			if(b%2==1) res=res*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return (int)res;
	}
	inline int toint(char c){
		if('0'<=c&&c<='9') return c-'0';
		else return c-'A'+10;
	}
	inline char tochar(int a){
		if(0<=a&&a<=9) return a+'0';
		else return a+'A'-10;
	}
	inline std::string forms(const std::string& s){
		int i=s.size();
		for(;i>1&&s[i-1]=='0';i--);
		return s.substr(0,i);
	}
	inline bool ucmp(const std::string& a,const std::string& b){
		if(a.size()<b.size()) return true;
		if(a.size()>b.size()) return false;
		for(int i=(int)a.size()-1;i>=0;i--){
			if(a[i]>b[i]) return false;
			if(a[i]<b[i]) return true;
		}
		return false;
	}
	inline std::string usub(std::string a,std::string b){
		bool flag=false;
		std::string ans="";
		if(ucmp(a,b)){
			flag=true;
			std::swap(a,b);
		}
		int now=0;
		for(int i=0;i<(int)a.size();i++){
			int x;
			if(i<(int)b.size()) x=toint(b[i]);
			else x=0;
			if(toint(a[i])-now<x){
				ans+=tochar(toint(a[i])+base-now-x);
				now=1;
			}else{
				ans+=tochar(toint(a[i])-now-x);
				now=0;
			}
		}
		ans=forms(ans);
		if(flag) ans=ans+"-";
		return ans;
	}
	inline std::string uadd(const std::string& a,const std::string& b){
		std::string ans="";
		int nx=0,now=0,len=std::max(a.size(),b.size());
		for(int i=0;i<len;i++){
			nx=0;
			if(i<(int)a.size()) nx+=toint(a[i]);
			if(i<(int)b.size()) nx+=toint(b[i]);
			nx+=now;
			now=0;
			if(nx>=base){
				now=1;
				nx-=base;
			}
			ans+=tochar(nx);
		}
		ans+=tochar(now);
		return forms(ans);
	}
	inline void ntt(std::vector<int>& a,bool b){
		int n=a.size();
		std::vector<int>to(n,0);
		for(int i=0;i<n;i++){
			to[i]=to[i>>1]>>1;
			if(i&1) to[i]|=(n>>1);
			if(i<to[i]) std::swap(a[i],a[to[i]]);
		}
		for(int l=2;l<=n;l<<=1){
			int wl=powmod(g,(mod-1)/l);
			if(b) wl=powmod(wl,mod-2);
			for(int i=0;i<n;i+=l){
				long long w=1;
				int mid=l>>1;
				for(int j=0;j<mid;j++){
					int x=a[i+j],y=w*a[i+j+mid]%mod;
					a[i+j]=(1ll*x+y)%mod;
					a[i+j+mid]=(1ll*x-y+mod)%mod;
					w=w*wl%mod;
				}
			}
		}
		if(b){
			int nf=powmod(n,mod-2);
			for(int i=0;i<n;i++) a[i]=1ll*a[i]*nf%mod;
		}
	}
	inline std::string umul(const std::string& a,const std::string& b){
		std::vector<int>va,vb;
		for(int i=0;i<(int)a.size();i++) va.push_back(toint(a[i]));
		for(int i=0;i<(int)b.size();i++) vb.push_back(toint(b[i]));
		int n=1;
		while(n<(int)va.size()+(int)vb.size()-1) n<<=1;
		va.resize(n);
		vb.resize(n);
		ntt(va,false);
		ntt(vb,false);
		for(int i=0;i<(int)va.size();i++) va[i]=1ll*va[i]*vb[i]%mod;
		ntt(va,true);
		for(int i=0;i<(int)va.size();i++){
			if(i<(int)va.size()-1) va[i+1]+=va[i]/base;
			else if(va[i]/base>0) va.push_back(va[i]/base);
			va[i]%=base;
		}
		std::string ans;
		for(int i=0;i<(int)va.size();i++) ans+=tochar(va[i]);
		return forms(ans);
	}
	inline std::pair<std::string,std::string> udiv(const std::string& a,const std::string& b){
		if(b=="0") throw std::runtime_error("除以零");
		if(a=="0") return {"0","0"};
		std::string r="0";
		std::string hq="";
		std::string na[44];
		na[0]="0";
		for(int nq=1;nq<base;nq++) na[nq]=uadd(na[nq-1],b);
		for(int i=(int)a.size()-1;i>=0;i--){
			r="0"+r;
			r=uadd(r,std::string(1,a[i]));
			int nq=base-1;
			while(nq>=0){
				if(!ucmp(r,na[nq])){
					r=usub(r,na[nq]);
					break;
				}
				nq--;
			}
			hq+=tochar(nq);
		}
		std::string q=hq;
		std::reverse(q.begin(),q.end());
		return {forms(q),forms(r)};
	}
	inline std::string lltostr(long long a){
		std::string s;
		if(a==0) return "0";
		unsigned long long x=ullabs(a);
		while(x){
			s+=tochar(x%base);
			x/=base;
		}
		if(a<0) s+="-";
		return s;
	}
	class bnum{
	private:
		bool sign;
		std::string num;
		void form(){
			num=forms(num);
			if((int)num.size()==1&&num[0]=='0') sign=true;
		}
	public:
		bnum():sign(true),num("0"){}
		bnum(bool b,std::string s):sign(b),num(s){
			form();
		}
		bnum(std::string s){
			if(!s.size()){
				num="0";
				sign=true;
			}else{
				if(s[(int)s.size()-1]=='-'){
					num=s.substr(0,(int)s.size()-1);
					sign=false;
				}else if(s[(int)s.size()-1]=='+'){
					num=s.substr(0,(int)s.size()-1);
					sign=true;
				}else{
					num=s;
					sign=true;
				}
			}
			if((int)num.size()==0) num="0";
			form();
		}
		bnum(long long x):bnum(lltostr(x)){}
		bnum(int x):bnum((long long)x){}
		explicit operator bool() const{
			return num!="0";
		}
		std::string get_num() const{
			std::string ans=num;
			reverse(ans.begin(),ans.end());
			return ans;
		}
		bool get_sign() const{return sign;}
		bnum& operator=(const bnum& other)=default;
		bnum& operator+=(const bnum& a){
			if(sign==a.sign){
				num=uadd(a.num,num);
				return *this;
			}else{
				num=usub(num,a.num);
				if(num[(int)num.size()-1]=='-'){
					sign=!sign;
					num=num.substr(0,(int)num.size()-1);
				}
				form();
				return *this;
			}
		}
		bnum& operator-=(const bnum& a){
			if(sign!=a.sign){
				num=uadd(a.num,num);
				return *this;
			}else{
				num=usub(num,a.num);
				if(num[(int)num.size()-1]=='-'){
					sign=!sign;
					num=num.substr(0,(int)num.size()-1);
				}
				form();
				return *this;
			}
		}
		bnum& operator*=(const bnum& a){
			num=umul(num,a.num);
			sign=(sign==a.sign);
			form();
			return *this;
		}
		bnum& operator/=(const bnum& a){
			num=udiv(num,a.num).first;
			sign=(sign==a.sign);
			form();
			return *this;
		}
		bnum& operator%=(const bnum& a){
			num=udiv(num,a.num).second;
			form();
			return *this;
		}
		bnum& operator++(){
			*this+=bnum(1);
			return *this;
		}
		bnum operator++(int){
			bnum old=*this;
			++(*this);
			return old;
		}
		bnum& operator--(){
			*this-=bnum(1);
			return *this;
		}
		bnum operator--(int){
			bnum old=*this;
			--(*this);
			return old;
		}
		friend bool operator==(const bnum& a,const bnum& b){
			if(a.sign!=b.sign) return false;
			if(a.num.size()!=b.num.size()) return false;
			for(int i=0;i<(int)a.num.size();i++){
				if(a.num[i]!=b.num[i]) return false;
			}
			return true;
		}
		friend bool operator<(const bnum& a,const bnum& b){
			if(a.sign&&!b.sign) return false;
			if(!a.sign&&b.sign) return true;
			if(a.sign) return ucmp(a.num,b.num);
			else return ucmp(b.num,a.num);
		}
		friend bool operator>(const bnum& a,const bnum& b){
			if(a.sign&&!b.sign) return true;
			if(!a.sign&&b.sign) return false;
			if(a.sign) return ucmp(b.num,a.num);
			else return ucmp(a.num,b.num);
		}
		friend bool operator<=(const bnum& a,const bnum& b){
			return !(a>b);
		}
		friend bool operator>=(const bnum& a,const bnum& b){
			return !(a<b);
		}
		friend bnum operator+(const bnum& a,const bnum& b){
			std::string ans;
			bool s=a.sign;
			if(a.sign==b.sign) ans=uadd(a.num,b.num);
			else{
				ans=usub(a.num,b.num);
				if(ans[(int)ans.size()-1]=='-'){
					s=!s;
					ans=ans.substr(0,(int)ans.size()-1);
				}
			}
			return bnum(s,ans);
		}
		friend bnum operator-(const bnum& a,const bnum& b){
			std::string ans;
			bool s=a.sign;
			if(a.sign!=b.sign) ans=uadd(a.num,b.num);
			else{
				ans=usub(a.num,b.num);
				if(ans[(int)ans.size()-1]=='-'){
					s=!s;
					ans=ans.substr(0,(int)ans.size()-1);
				}
			}
			return bnum(s,ans);
		}
		friend bnum operator*(const bnum& a,const bnum& b){
			std::string ans=umul(a.num,b.num);
			bool s=(a.sign==b.sign);
			return bnum(s,ans);
		}
		friend bnum operator/(const bnum& a,const bnum& b){
			std::string ans=udiv(a.num,b.num).first;
			bool s=(a.sign==b.sign);
			return bnum(s,ans);
		}
		friend bnum operator%(const bnum& a,const bnum& b){
			std::string ans=udiv(a.num,b.num).second;
			bool s=a.sign;
			return bnum(s,ans);
		}
		friend bnum operator-(const bnum& a){
			return bnum(!a.sign,a.num);
		}
		friend std::ostream& operator<<(std::ostream& o,const bnum& x){
			if(!x.sign) o<<'-';
			for(int i=(int)x.num.size()-1;i>=0;i--) o<<x.num[i];
			return o;
		}
		friend std::istream& operator>>(std::istream& i,bnum& x){
			std::string s;
			i>>s;
			if(i.fail()) return i;
			for(int j=0;j<(int)s.size();j++){
				if(!(j==0&&(s[j]=='+'||s[j]=='-'))&&!(('0'<=s[j]&&s[j]<='0'+std::min(base-1,9))||('A'<=s[j]&&s[j]<='A'+base-11))){
					i.setstate(std::ios::failbit);
					return i;
				}
			}
			std::reverse(s.begin(),s.end());
			x=bnum(s);
			return i;
		}
	};
	inline bnum abs(bnum a){
		if(a<0) a=-a;
		return a;
	}
	inline bnum gcd(bnum a,bnum b){
		if(a<b) std::swap(a,b);
		return (b==0)?a:gcd(b,a%b);
	}
	class frac{
	private:
		bnum num;
		bnum den;
		void form(){
			if(den==0) throw std::runtime_error("分母为零 或 除以零");
			if(den<0){
				num=-num;
				den=-den;
			}
			bnum g=gcd(abs(num),den);
			num/=g;
			den/=g;
		}
	public:
		frac(bnum n=0,bnum d=1):num(n),den(d){
			form();
		}
		bnum get_num() const{return num;}
		bnum get_den() const{return den;}
		frac& operator=(const frac& other)=default;
		frac& operator+=(const frac& f){
			num=num*f.den+f.num*den;
			den=den*f.den;
			form();
			return *this;
		}
		frac& operator-=(const frac& f){
			num=num*f.den-f.num*den;
			den=den*f.den;
			form();
			return *this;
		}
		frac& operator*=(const frac& f){
			num*=f.num;
			den*=f.den;
			form();
			return *this;
		}
		frac& operator/=(const frac& f){
			num*=f.den;
			den*=f.num;
			form();
			return *this;
		}
		friend frac operator+(const frac& a,const frac& b){
			return frac(a.num*b.den+b.num*a.den,a.den*b.den);		
		}
		friend frac operator-(const frac& a,const frac& b){
			return frac(a.num*b.den-b.num*a.den,a.den*b.den);		
		}
		friend frac operator*(const frac& a,const frac& b){
			return frac(a.num*b.num,a.den*b.den);		
		}
		friend frac operator/(const frac& a,const frac& b){
			return frac(a.num*b.den,a.den*b.num);		
		}
		friend frac operator-(const frac& a){
			return frac(-a.num,a.den);
		}
		friend bool operator==(const frac& a,const frac& b){
			if(a.num==b.num&&a.den==b.den) return true;
			return false;
		}
		friend bool operator<(const frac& a,const frac& b){
			if(a.num*b.den<b.num*a.den) return true;
			return false;
		}
		friend bool operator>(const frac& a,const frac& b){
			if(a.num*b.den>b.num*a.den) return true;
			return false;
		}
		friend bool operator<=(const frac& a,const frac& b){
			return !(a>b);
		}
		friend bool operator>=(const frac& a,const frac& b){
			return !(a<b);
		}
		friend std::ostream& operator<<(std::ostream& o,const frac& f){
			if(f.den==1) o<<f.num;
			else o<<f.num<<'/'<<f.den;
			return o;
		}
		friend std::istream& operator>>(std::istream& i,frac& f){
			bnum n,d=1;
			char s=0;
			if(!(i>>n)) return i;
			if(i.peek()=='/'){
				i>>s;
				if(!(i>>d)) return i;
			}
			if(d==0){
				i.setstate(std::ios::failbit);
				return i;
			}
			f=frac(n,d);
			return i;
		}
	};
}
#endif

--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
扩展-解析几何：

#ifndef _EX_GEO_H
#define _EX_GEO_H
#include<bits/stdc++.h>
namespace ana_geo{
	inline std::pair<double,double>StToSi(double a,double b,double c){
		if(b==0) throw std::invalid_argument("无法转为斜截式");
		//ax+by+c=0 to y=kx+b
		return {-a/b,-c/b};
	}
	inline std::pair<double,std::pair<double,double>>SiToSt(double k,double b){
		//y=kx+b to ax+by+c=0
		return {-k,{1,-b}};
	}
	inline double dis_ptp(double x,double y,double xx,double yy){
		//point to point
		return std::hypot(x-xx,y-yy);
	} 
	inline double dis_ptl(double x,double y,double a,double b,double c){
		if(a==0&&b==0) throw std::invalid_argument("直线不合法");
	//	return dis_ptp(x,y,(b*b*x-a*b*y-a*c)/(a*a+b*b),(a*a*y-a*b*x-b*c)/(a*a+b*b));
		return fabs(a*x+b*y+c)/std::hypot(a,b);//sqrt(a*a+b*b) 
	}
	inline double dis_ltl_prl(double a1,double b1,double c1,double a2,double b2,double c2){
		if(b1!=0) return dis_ptl(0,-c1/b1,a2,b2,c2);
		else return dis_ptl(-c1/a1,0,a2,b2,c2);
	}
	inline bool is_prl(double a1,double b1,double c1,double a2,double b2,double c2){
		if(fabs(a1*b2-a2*b1)>1e-9*std::hypot(a1,b1)*std::hypot(a2,b2)) return false;
		return true;
	}
	inline std::pair<bool,double>dis_ltl(double a1,double b1,double c1,double a2,double b2,double c2){
		if(a1==0&&b1==0) throw std::invalid_argument("直线不合法");
		if(a2==0&&b2==0) throw std::invalid_argument("直线不合法");
		if(is_prl(a1,b1,c1,a2,b2,c2)) return {true,dis_ltl_prl(a1,b1,c1,a2,b2,c2)};
		else return {false,0.0};
	}
	inline int LandC(double a,double b,double c,double d,double e,double f,bool k){
		if(a==0&&b==0) throw std::invalid_argument("直线不合法");
		if(k){
			//ax+by+c=0 & x^2+y^2+dx+ey+f=0
			if(d*d+e*e-4*f<=0) throw std::invalid_argument("圆不合法");
			double x=-d/2,y=-e/2,r=sqrt(d*d+e*e-4*f)/2;
			double dk=dis_ptl(x,y,a,b,c);
			if(dk>r+1e-9) return -1;
			if(fabs(dk-r)<=1e-9) return 0;
			return 1;
		}else{
			//ax+by+c=0 & (x-d)^2+(y-e)^2=f^2
			if(f<=0) throw std::invalid_argument("圆不合法");
			double dk=dis_ptl(d,e,a,b,c);
			if(dk>f+1e-9) return -1;
			if(fabs(dk-f)<=1e-9) return 0;
			return 1;
		}
	}
	inline int CandC(double a,double b,double c,bool k1,double d,double e,double f,bool k2){
		//x^2+y^2+ax+by+c=0/(x-a)^2+(y-b)^2=c^2 & x^2+y^2+dx+ey+f=0/(x-d)^2+(y-e)^2=f^2
		if(k1&&a*a+b*b-4*c<=0) throw std::invalid_argument("圆不合法");
		if(k2&&d*d+e*e-4*f<=0) throw std::invalid_argument("圆不合法");
		if(!k1&&c<=0) throw std::invalid_argument("圆不合法");
		if(!k2&&f<=0) throw std::invalid_argument("圆不合法");
		double x,y,r,xx,yy,rr;
		if(k1) x=-a/2,y=-b/2,r=sqrt(a*a+b*b-4*c)/2;
		else x=a,y=b,r=c;
		if(k2) xx=-d/2,yy=-e/2,rr=sqrt(d*d+e*e-4*f)/2;
		else xx=d,yy=e,rr=f;
		double dk=dis_ptp(x,y,xx,yy);
		if(dk>r+rr+1e-9) return -2;
		if(fabs(dk-r-rr)<=1e-9) return -1;
		if(std::max(r,rr)-std::min(r,rr)+1e-9<dk&&dk<r+rr-1e-9) return 0;
		if(fabs(dk-std::max(r,rr)+std::min(r,rr))<=1e-9) return 1;
		if(dk<=1e-9&&fabs(r-rr)<=1e-9) return 3;
		return 2;
	}
}
#endif

--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
--用于分隔--
闲的没事写了个线段树：

#ifndef _SEG_TREES_H
#define _SEG_TREES_H
#include<vector>
#include<utility>
#include<algorithm>
namespace segt{
	template<typename T>
	class sum_segt{
	private:
		class node{
		public:
			int l,r,mid;
			T sum,add,mul;
		};
		std::vector<node>t;
		std::vector<T>a;
		void pushup(int u){
			t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
		}
		void apply(int u,T m,T x){
			t[u].sum=m*t[u].sum+x*(t[u].r-t[u].l+1);
			t[u].mul=m*t[u].mul;
			t[u].add=m*t[u].add+x;
		}
		void pushdown(int u){
			if(t[u].mul==1&&t[u].add==0) return;
			apply(u<<1,t[u].mul,t[u].add);
			apply(u<<1|1,t[u].mul,t[u].add);
			t[u].mul=1;
			t[u].add=0;	
		}
		void build(int u,int l,int r){
			t[u].mul=1;
			t[u].add=0;
			t[u].l=l;
			t[u].r=r;
			t[u].mid=(l+r)>>1;
			if(l==r){
				t[u].sum=a[l-1];
				return;
			}
			build(u<<1,l,t[u].mid);
			build(u<<1|1,t[u].mid+1,r);
			pushup(u);
		}
		void update(int u,int l,int r,T m,T x){
			if(l<=t[u].l&&t[u].r<=r){
				apply(u,m,x);
				return;
			}
			pushdown(u);
			if(l<=t[u].mid) update(u<<1,l,r,m,x);
			if(r>t[u].mid) update(u<<1|1,l,r,m,x);
			pushup(u);
		}
		T query(int u,int l,int r){
			if(l<=t[u].l&&t[u].r<=r) return t[u].sum;
			pushdown(u);
			T ans=0;
			if(l<=t[u].mid) ans+=query(u<<1,l,r);
			if(r>t[u].mid) ans+=query(u<<1|1,l,r);
			return ans;
		}
	public:
		sum_segt(std::vector<T>v){
			a=v;
			t.resize(4*v.size());
			build(1,1,v.size());
		}
		void add(int l,int r,T k){
			update(1,l,r,1,k);
		}
		void add(int x,T k){
			update(1,x,x,1,k);
		}
		void mul(int l,int r,T k){
			update(1,l,r,k,0);
		}
		void mul(int x,T k){
			update(1,x,x,k,0);
		}
		void set(int l,int r,T k){
			update(1,l,r,0,k);
		}
		void set(int x,T k){
			update(1,x,x,0,k);
		}
		T sum(int l,int r){
			return query(1,l,r);
		}
		T val(int x){
			return query(1,x,x);
		}
	};
	template<typename T>
	class exm_segt{
	private:
		class node{
		public:
			int l,r,mid;
			T maxx,minx;
			int maxn,minn;
			T add,mul;
		};
		std::vector<node>t;
		std::vector<T>a;
		void pushup(int u){
			if(t[u<<1].maxx>t[u<<1|1].maxx){
				t[u].maxx=t[u<<1].maxx;
				t[u].maxn=t[u<<1].maxn;
			}else if(t[u<<1].maxx<t[u<<1|1].maxx){
				t[u].maxx=t[u<<1|1].maxx;
				t[u].maxn=t[u<<1|1].maxn;
			}else{
				t[u].maxx=t[u<<1].maxx;
				t[u].maxn=t[u<<1].maxn+t[u<<1|1].maxn;
			}
			if(t[u<<1].minx<t[u<<1|1].minx){
				t[u].minx=t[u<<1].minx;
				t[u].minn=t[u<<1].minn;
			}else if(t[u<<1].minx>t[u<<1|1].minx){
				t[u].minx=t[u<<1|1].minx;
				t[u].minn=t[u<<1|1].minn;
			}else{
				t[u].minx=t[u<<1].minx;
				t[u].minn=t[u<<1].minn+t[u<<1|1].minn;
			}
		}
		void apply(int u,T m,T x){
			T nmaxx=t[u].maxx,nminx=t[u].minx;
			int nmaxn=t[u].maxn,nminn=t[u].minn;
			if(m==0){
				t[u].maxx=t[u].minx=x;
				t[u].maxn=t[u].minn=t[u].r-t[u].l+1;
			}else if(m>0){
				t[u].maxx=m*nmaxx+x;
				t[u].minx=m*nminx+x;
			}else{
				t[u].maxx=m*nminx+x;
				t[u].minx=m*nmaxx+x;
				t[u].maxn=nminn;
				t[u].minn=nmaxn;
			}
			t[u].mul=m*t[u].mul;
			t[u].add=m*t[u].add+x;
		}
		void pushdown(int u){
			if(t[u].mul==1&&t[u].add==0) return;
			apply(u<<1,t[u].mul,t[u].add);
			apply(u<<1|1,t[u].mul,t[u].add);
			t[u].mul=1;
			t[u].add=0;	
		}
		void build(int u,int l,int r){
			t[u].mul=1;
			t[u].add=0;
			t[u].l=l;
			t[u].r=r;
			t[u].mid=(l+r)>>1;
			if(l==r){
				t[u].maxx=t[u].minx=a[l-1];
				t[u].maxn=t[u].minn=1;
				return;
			}
			build(u<<1,l,t[u].mid);
			build(u<<1|1,t[u].mid+1,r);
			pushup(u);
		}
		void update(int u,int l,int r,T m,T x){
			if(l<=t[u].l&&t[u].r<=r){
				apply(u,m,x);
				return;
			}
			pushdown(u);
			if(l<=t[u].mid) update(u<<1,l,r,m,x);
			if(r>t[u].mid) update(u<<1|1,l,r,m,x);
			pushup(u);
		}
		std::pair<T,int>query_max(int u,int l,int r){
			if(l<=t[u].l&&t[u].r<=r) return {t[u].maxx,t[u].maxn};
			pushdown(u);
			if(r<=t[u].mid) return query_max(u<<1,l,r);
			if(l>t[u].mid) return query_max(u<<1|1,l,r);
			auto le=query_max(u<<1,l,r),ri=query_max(u<<1|1,l,r);
			if(le.first>ri.first) return le;
			else if(le.first<ri.first) return ri;
			return {le.first,le.second+ri.second};
		}
		std::pair<T,int>query_min(int u,int l,int r){
			if(l<=t[u].l&&t[u].r<=r) return {t[u].minx,t[u].minn};
			pushdown(u);
			if(r<=t[u].mid) return query_min(u<<1,l,r);
			if(l>t[u].mid) return query_min(u<<1|1,l,r);
			auto le=query_min(u<<1,l,r),ri=query_min(u<<1|1,l,r);
			if(le.first<ri.first) return le;
			else if(le.first>ri.first) return ri;
			return {le.first,le.second+ri.second};
		}
	public:
		exm_segt(std::vector<T>v){
			a=v;
			t.resize(4*v.size());
			build(1,1,v.size());
		}
		void add(int l,int r,T k){
			update(1,l,r,1,k);
		}
		void add(int x,T k){
			update(1,x,x,1,k);
		}
		void mul(int l,int r,T k){
			update(1,l,r,k,0);
		}
		void mul(int x,T k){
			update(1,x,x,k,0);
		}
		void set(int l,int r,T k){
			update(1,l,r,0,k);
		}
		void set(int x,T k){
			update(1,x,x,0,k);
		}
		T max(int l,int r){
			return query_max(1,l,r).first;
		}
		T min(int l,int r){
			return query_min(1,l,r).first;
		}
		int max_cnt(int l,int r){
			return query_max(1,l,r).second;
		}
		int min_cnt(int l,int r){
			return query_min(1,l,r).second;
		}
		T val(int x){
			return query_max(1,x,x).first;
		}
	};
}
#endif

#ifndef _RED_BLACK_TREE_H
#define _RED_BLACK_TREE_H
#include<stack>
#include<vector>
#include<utility>
#include<algorithm>
#include<stdexcept>
namespace rbt{
	template<typename T>
	class RBT{
	private:
		enum color_t{R,B};
		struct node{
			T v;
			node* fa;
			node* l;
			node* r;
			color_t color;
			int sz,cnt;
			node(T x):v(x),color(R),l(nullptr),r(nullptr),fa(nullptr),sz(1),cnt(1){}
			void pushup(){
				sz=l->sz+r->sz+cnt;
			}
		};
		node* root;
		node* nil;
		void lrot(node* x){
			node* y=x->r;
			x->r=y->l;
			if(y->l!=nil) y->l->fa=x;
			y->fa=x->fa;
			if(x->fa==nil) root=y;
			else if(x==x->fa->l) x->fa->l=y;
			else x->fa->r=y;
			y->l=x;
			x->fa=y;
			x->pushup();
			y->pushup();
		}
		void rrot(node* x){
			node* y=x->l;
			x->l=y->r;
			if(y->r!=nil) y->r->fa=x;
			y->fa=x->fa;
			if(x->fa==nil) root=y;
			else if(x==x->fa->l) x->fa->l=y;
			else x->fa->r=y;
			y->r=x;
			x->fa=y;
			x->pushup();
			y->pushup();
		}
		node* findn(T x) const{
			node* p=root;
			while(p!=nil){
				if(x<p->v) p=p->l;
				else if(x>p->v) p=p->r;
				else return p;
			}
			return nil;
		}
		node* init(T v,node* f,color_t c,int il){
			node* p=new node(v);
			p->color=c;
			p->fa=f;
			p->l=nil;
			p->r=nil;
			if(f==nil) root=p;
			else{
				if(il==-1) f->l=p;
				else if(il==1) f->r=p; 
			}
			return p;
		}
		void ist(T v){
			node* last=nil;
			node* p=root;
			while(p!=nil){
				last=p;
				if(v<p->v) p=p->l;
				else if(v>p->v) p=p->r;
				else{
					p->cnt++;
					return;
				}
			}
			if(last==nil) p=root=init(v,nil,B,0);
			else p=init(v,last,R,(v<last->v?-1:1));
			while(p->fa->color==R){
				if(p->fa==p->fa->fa->l){
					if(p->fa->fa->r->color==R){
						p->fa->fa->color=R;
						p->fa->color=B;
						p->fa->fa->r->color=B;
						p=p->fa->fa; 
					}else{
						if(p==p->fa->r){
							lrot(p->fa);
							p=p->l;
						}
						rrot(p->fa->fa);
						p->fa->color=B;
						p->fa->r->color=R;
					}
				}else{
					if(p->fa->fa->l->color==R){
						p->fa->fa->color=R;
						p->fa->color=B;
						p->fa->fa->l->color=B;
						p=p->fa->fa;
					}else{
						if(p==p->fa->l){
							rrot(p->fa);
							p=p->r;
						}
						lrot(p->fa->fa);
						p->fa->color=B;
						p->fa->l->color=R;
					}
				}
			}
			root->color=B;
		}
		void exch(node* x,node* y){
			std::swap(x->v,y->v);
			std::swap(x->cnt,y->cnt);
		}
		bool del(T v){
			node* p=findn(v);
			if(p==nil) return false;
			if(--(p->cnt)>0) return true;
			if(p->l!=nil){
				node* g=p->l;
				while(g->r!=nil) g=g->r;
				exch(p,g);
				p=g;
			}else if(p->r!=nil){
				node* g=p->r;
				while(g->l!=nil) g=g->l;
				exch(p,g);
				p=g;
			}
			if(p->l!=nil){
				exch(p,p->l);
				p=p->l;
			}else if(p->r!=nil){
				exch(p,p->r);
				p=p->r;
			}
			node* g=p;
			for(;g!=nil;g=g->fa) g->pushup();
			if(p->color==R){
				if(p==p->fa->l) p->fa->l=nil;
				else p->fa->r=nil;
				delete p;
				return true;
			}
			g=p;
			while(p!=root){
				if(p==p->fa->l){
					if(p->fa->r->color==R){
						lrot(p->fa);
						p->fa->color=R;
						p->fa->fa->color=B;
					}else{
						if(p->fa->r->l->color==B&&p->fa->r->r->color==B){
							if(p->fa->color==R){
								p->fa->color=B;
								p->fa->r->color=R;
								break;
							}else{
								p->fa->r->color=R;
								p=p->fa;
							}
						}else{
							if(p->fa->r->r->color==B){
								rrot(p->fa->r);
								p->fa->r->color=B;
								p->fa->r->r->color=R;
							}else{
								lrot(p->fa);
								if(p->fa->color==R) p->fa->fa->color=R;
								p->fa->color=B;
								p->fa->fa->r->color=B;
								break;
							}
						}
					}
				}else{
					if(p->fa->l->color==R){
						rrot(p->fa);
						p->fa->color=R;
						p->fa->fa->color=B;
					}else{
						if(p->fa->l->l->color==B&&p->fa->l->r->color==B){
							if(p->fa->color==R){
								p->fa->color=B;
								p->fa->l->color=R;
								break;
							}else{
								p->fa->l->color=R;
								p=p->fa;
							}
						}else{
							if(p->fa->l->l->color==B){
								rrot(p->fa->l);
								p->fa->l->color=B;
								p->fa->l->l->color=R;
							}else{
								rrot(p->fa);
								if(p->fa->color==R) p->fa->fa->color=R;
								p->fa->color=B;
								p->fa->fa->l->color=B;
								break;
							}
						}
					}
				}
			}
			if(g==root) root=nil;
			else if(g==g->fa->l) g->fa->l=nil;
			else g->fa->r=nil;
			delete g;
			return true;
		}
		std::pair<bool,T>th(int k) const{
			node* p=root;
			while(p!=nil){
				if(k<=p->l->sz) p=p->l;
				else if(k<=p->l->sz+p->cnt) return {true,p->v};
				else{
					k=k-p->l->sz-p->cnt;
					p=p->r;
				}
			}
			return {false,T{}};
		}
		int rank(T v) const{
			int ans=0;
			node* p=root;
			while(p!=nil){
				if(v<p->v) p=p->l;
				else if(v==p->v){
					ans+=p->l->sz;
					break;
				}else{
					ans+=p->l->sz+p->cnt;
					p=p->r;
				}
			}
			return ans;
		}
	public:
		RBT(){
			nil=new node(0);
			nil->fa=nil->l=nil->r=nil;
			nil->sz=0;
			nil->cnt=0;
			nil->color=B;
			root=nil;
		}
		~RBT(){
			if(root==nil){
				delete nil;
				return;
			}
			std::vector<node*>v;
			std::stack<node*>s;
			s.push(root);
			while(!s.empty()){
				node* p=s.top();
				s.pop();
				v.push_back(p);
				if(p->l!=nil) s.push(p->l);
				if(p->r!=nil) s.push(p->r);
			}
			for(node* p:v) delete p;
			delete nil;
		}
		void insert(T v){
			ist(v);
		}
		bool erase(T v){
			return del(v);
		}
		int find(T v) const{
			node* p=findn(v);
			if(p==nil) return 0;
			return rank(v)+1;
		}
		int lower(T v) const{
			return rank(v);
		}
		int count(T v) const{
			node* p=findn(v);
			if(p==nil) return 0;
			return p->cnt;
		}
		T kth(int k) const{
			std::pair<bool,T>ans=th(k);
			if(ans.first) return ans.second;
			throw std::out_of_range("kth: k out of range");
		}
		T pre(T v) const{
			return kth(lower(v));
		}
		T nxt(T v) const{
			return kth(lower(v)+count(v)+1);
		}
		bool empty() const{
			return (root==nil);
		}
		void clear(){
			if(!empty()){
				std::vector<node*>v;
				std::stack<node*>s;
				s.push(root);
				while(!s.empty()){
					node* p=s.top();
					s.pop();
					v.push_back(p);
					if(p->l!=nil) s.push(p->l);
					if(p->r!=nil) s.push(p->r);
				}
				for(node* p:v) delete p;
				root=nil;
			}
			nil->fa=nil->l=nil->r=nil;
		}
	};
}
#endif

现在写完了
部分内容使用了AI帮忙挑错，但绝对没有一行代码是AI写的。