C++模板

//-std=c++14
//-O2
//#pragma GCC optimize("Ofast")
//next_permutation(a+1,a+1+n)
#include<bits/stdc++.h>
#define bint BigInteger
#define hh puts("");
#define yes puts("yes");
#define no puts("no");
#define YES puts("YES");
#define NO puts("NO");
#define open(x) freopen(x,"r",stdin);
#define write(x) freopen(x,"w",stdout);
#define file(x,y) freopen(x,"r",stdin);freopen(y,"w",stdout);
#define printa(a,n) for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
#define prints(a,n) for(int i=0;i<n;i++)printf("%c",a[i]);puts("");
using namespace std;
mt19937 rd(time(NULL)^clock());
typedef long long ll;typedef unsigned long long ull;
const int N = 101,dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
const double pi = acos(-1),e = exp(1);
class BigInteger{static const int BASE=100000000;static const int WIDTH=8;public:vector<int>s;BigInteger&clean(){while(!s.back()&&s.size()>1)s.pop_back();return*this;}BigInteger(unsigned long long num=0){*this=num;}BigInteger(string s){*this=s;}BigInteger&operator=(long long num){s.clear();do{s.push_back(num%BASE);num/=BASE;}while(num>0);return*this;}BigInteger&operator=(const string&str){s.clear();int x,len=(str.length()-1)/WIDTH+1;for(int i=0;i<len;i++){int end=str.length()-i*WIDTH;int start=max(0,end-WIDTH);sscanf(str.substr(start,end-start).c_str(),"%d",&x);s.push_back(x);}return this->clean();}BigInteger operator+(const BigInteger&b)const{BigInteger c;c.s.clear();for(int i=0,g=0;;i++){if(g==0&&i>=s.size()&&i>=b.s.size())break;int x=g;if(i<s.size())x+=s[i];if(i<b.s.size())x+=b.s[i];c.s.push_back(x%BASE);g=x/BASE;}return c;}BigInteger operator-(const BigInteger&b)const{assert(b<=*this);BigInteger c;c.s.clear();for(int i=0,g=0;;i++){if(g==0&&i>=s.size()&&i>=b.s.size())break;int x=s[i]+g;if(i<b.s.size())x-=b.s[i];if(x<0){g=-1;x+=BASE;}else g=0;c.s.push_back(x);}return c.clean();}BigInteger operator*(const BigInteger&b)const{int i,j;unsigned long long g;vector<unsigned long long>v(s.size()+b.s.size(),0);BigInteger c;c.s.clear();for(i=0;i<s.size();i++)for(j=0;j<b.s.size();j++)v[i+j]+=ull(s[i])*b.s[j];for(i=0,g=0;;i++){if(g==0&&i>=v.size())break;unsigned long long x=v[i]+g;c.s.push_back(x%BASE);g=x/BASE;}return c.clean();}BigInteger operator/(const BigInteger&b)const{assert(b>0);BigInteger c=*this,m;for(int i=s.size()-1;i>-1;i--){m=m*BASE+s[i];c.s[i]=bsearch(b,m);m-=b*c.s[i];}return c.clean();}BigInteger operator%(const BigInteger&b)const{BigInteger c=*this;BigInteger m;for(int i=s.size()-1;i>-1;i--){m=m*BASE+s[i];c.s[i]=bsearch(b,m);m-=b*c.s[i];}return m;}int bsearch(const BigInteger&b,const BigInteger&m)const{int L=0,R=BASE-1,x;while(1){x=(L+R)>>1;if(b*x<=m){if(b*(x+1)>m)return x;else L=x;}else R=x;}}BigInteger&operator+=(const BigInteger&b){*this=*this+b;return*this;}BigInteger&operator-=(const BigInteger&b){*this=*this-b;return*this;}BigInteger&operator*=(const BigInteger&b){*this=*this*b;return*this;}BigInteger&operator/=(const BigInteger&b){*this=*this/b;return*this;}BigInteger&operator%=(const BigInteger&b){*this=*this%b;return*this;}bool operator<(const BigInteger&b)const{if(s.size()!=b.s.size())return s.size()<b.s.size();for(int i=s.size()-1;i;i--)if(s[i]!=b.s[i])return s[i]<b.s[i];return s[0]<b.s[0];}bool operator>(const BigInteger&b)const{return b<*this;}bool operator<=(const BigInteger&b)const{return!(b<*this);}bool operator>=(const BigInteger&b)const{return!(*this<b);}bool operator!=(const BigInteger&b)const{return b<*this||*this<b;}bool operator==(const BigInteger&b)const{return!(b<*this)&&!(b>*this);}};ostream&operator<<(ostream&out,const BigInteger&x){out<<x.s.back();for(int i=x.s.size()-2;i>-1;i--){char buf[20];sprintf(buf,"%08d",x.s[i]);for(int j=0;j<strlen(buf);j++)out<<buf[j];}return out;}istream&operator>>(istream&in,BigInteger&x){string s;if(!(in>>s))return in;x=s;return in;}
int ola_prime[N];
bool ola_isprime[N],sun_isprime[N/2];
ll fac[1000001];
bool ss(int n){int i;if(n<=1)return 0;if(n==2||n==3)return 1;if(n%6!=1&&n%6!=5||n%2==0)return 0;for(i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;}void make_sun(){int m=N/2;int i;for(i=1;i<=m;i++){int j=i,p=i+j+2*i*j;if(p>m)break;while(p<=m){sun_isprime[p]=1;j++;p=i+j+2*i*j;}}}bool isPrime(int n){if(n<2)return 0;if(n<=2)return 1;if((n&1)==0)return 0;return!sun_isprime[(n-1)/2];}void make_ola(){ola_isprime[1]=1;int i,j;for(i=2;i<=N;i++){if(!ola_isprime[i])ola_prime[++ola_prime[0]]=i;for(j=1;j<=ola_prime[0]&&i*ola_prime[j]<=N;j++){ola_isprime[i*ola_prime[j]]=1;if(i%ola_prime[j]==0)break;}}return;}ll pr[]={2,3,5,7,11,13,17,19,23,29,31,37};ll ksc(ll x,ll y,ll p){return(__int128_t)x*y%p;}ll qpow(ll x,ll y,ll p){ll res=1;while(y){if(y&1ll)res=ksc(res,x,p);y>>=1;x=ksc(x,x,p);}return res;}bool MR(ll x){for(int i=0;i<12;++i){ll P=pr[i],x0=x-1;if(x==P)return 1;if(x<P)return 0;if(qpow(P,x-1,x)!=1)return 0;while(x0%2==0){x0>>=1;ll Pow=qpow(P,x0,x);if(Pow==x-1)break;if(Pow!=1)return 0;}}return 1;}const int NNN=6e6+7,MMM=7,KKK=2*3*5*7*11*13*17;int prime[NNN],piii[NNN],phiii[KKK+7][MMM+7],product[MMM+7];bool ppppp[NNN];map<ll,ll>mppp;int INTTTT(){int cnt=0;ppppp[0]=ppppp[1]=true;for(int i=2;i<NNN;i++){if(!ppppp[i])prime[++cnt]=i;piii[i]=cnt;for(int j=1;j<=cnt&&i*prime[j]<NNN;j++){ppppp[i*prime[j]]=true;if(i%prime[j]==0)break;}}product[0]=1;for(int i=0;i<=KKK;i++){phiii[i][0]=i;}for(int i=1;i<=MMM;i++){product[i]=product[i-1]*prime[i];for(int j=1;j<=KKK;j++){phiii[j][i]=phiii[j][i-1]-phiii[j/prime[i]][i-1];}}return cnt;}ll sqrt(ll n){ll ans=sqrt((double)n);while(ans*ans<=n)ans++;return ans-1;}ll get_euler(ll n,ll m){if(m==0)return n;if(m<=MMM)return phiii[n%product[m]][m]+n/product[m]*phiii[product[m]][m];if(n<=prime[m]*prime[m])return piii[n]-m+1;if(n<=prime[m]*prime[m]*prime[m]&&n<NNN){ll t=piii[sqrt(n)],ans=piii[n]-(m+t-2)*(t-m+1)/2;for(ll i=m+1;i<=t;i++){ans+=piii[n/prime[i]];}return ans;}return get_euler(n,m-1)-get_euler(n/prime[m],m-1);}ll cbrt(ll n){__int128 ans=1;while(ans*ans*ans<=n)ans++;return ans-1;}ll prime_count(ll n){if(n<NNN)return piii[n];if(mppp.count(n))return mppp[n];ll a=prime_count(cbrt(n)),b,c,t=sqrt(n),ans;b=prime_count(sqrt(t));c=prime_count(t);ans=get_euler(n,b)+(b+c-2)*(c-b+1)/2;for(ll i=b+1;i<=c;i++){ll x=n/prime[i];ans-=prime_count(x);if(i<=a){ll t=prime_count(sqrt(x));for(ll j=i;j<=t;j++){ans-=prime_count(x/prime[j])-(j-1);}}}return mppp[n]=ans;}ll get_nth_prime(ll n,ll max_ans,int cnt){if(n<=cnt)return prime[n];ll l=NNN,r=max_ans;while(l<r){ll mid=(l+r)>>1;if(prime_count(mid)>=n){r=mid;}else{l=mid+1;}}return l;}ll nth_prime(ll a){int cnt=INTTTT();return get_nth_prime(a,22801763489ll,cnt);}
int gcd(int a,int b);int lcm(int a,int b);int daoxu(int n);bool hw(int n);ll ksm(ll a,ll b,int c);int char_to_digit(char c);char digit_to_char(int x);void kprintl(int n,char s[],int m);void ktol(int n,char s[],int m);void strupper(char s[]);void strlower(char s[]);int qh(int n);void makejc(int n,ll p);ll C(ll n,ll m,ll p);ll jc(ll n,ll p);
namespace fastio{const int bufl=1<<20;const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};struct IN{FILE*IT;char ibuf[bufl],*is=ibuf,*it=ibuf;IN(){IT=stdin;}IN(char*a){IT=fopen(a,"r");}inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return*is++;}template<typename Temp>inline void getInt(Temp&a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}template<typename Temp>inline void getDouble(Temp&a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}IN&operator>>(char&a){a=getChar();return*this;}IN&operator>>(char*a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return*this;}IN&operator>>(string&a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return*this;}IN&operator>>(int&a){getInt(a);return*this;}IN&operator>>(long long&a){getInt(a);return*this;}IN&operator>>(__int128&a){getInt(a);return*this;}IN&operator>>(float&a){getDouble(a);return*this;}IN&operator>>(double&a){getDouble(a);return*this;}IN&operator>>(long double&a){getDouble(a);return*this;}};struct OUT{FILE*IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char*a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}inline void ChangEps(int x=6){Eps=x;}inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}inline void putChar(int a){*os++=a;if(os==ot)flush();}template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putInt(b);}OUT&operator<<(char a){putChar(a);return*this;}OUT&operator<<(char*a){while(*a>32)putChar(*a++);return*this;}OUT&operator<<(string a){for(auto c:a)putChar(c);return*this;}OUT&operator<<(int a){putInt(a);return*this;}OUT&operator<<(long long a){putInt(a);return*this;}OUT&operator<<(__int128 a){putInt(a);return*this;}OUT&operator<<(float a){putDouble(a);return*this;}OUT&operator<<(double a){putDouble(a);return*this;}OUT&operator<<(long double a){putDouble(a);return*this;}~OUT(){flush();}};}using fastio::IN;using fastio::OUT;IN fin;OUT fout;

#define endl '\n'
//#define cin fin
//#define cout fout



signed main()
{
	
    return 0;
}























































int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
	return a*b/gcd(a,b);
}

bool hw(int n)
{
	int a,b;
	a = n;
	b = 0;
	while(a)
	{
		b = b*10+a%10;
		a /= 10;
	}
	return n==b;
}
int daoxu(int n)
{
	
	int b=0;
	while(n)
	{
		b = b*10+n%10;
		n /= 10;
	}
	return b;
}
ll ksm(ll a,ll b,int c)
{
	a %= c;
	ll s = 1;
	while(b)
	{
		if(b&1)
			s = s*a%c;
		b >>= 1;
		a = a*a%c;
	}
	return s%c;
}
int char_to_digit(char c)
{
	if(c>='0'&&c<='9')
		return c-'0';
	else
		return c-'a'+10;
}
char digit_to_char(int x)
{
	if(x<=9)
		return x+'0';
	else
		return (x-10)+'a';
}
void kprintl(int n,char s[],int m)
{
	
	int cnt = 0,v = 0,l = strlen(s),i;
	char c[100001];
	for(i=0;i<l;i++)
		v = v*n+char_to_digit(s[i]);
	while(v!=0)
		c[cnt] = digit_to_char(v%m),v /= m,cnt++;
	for(i=cnt-1;i>=0;i--)
		putchar(c[i]);
	puts("");
		
}
void ktol(int n,char s[],int m)
{
	int cnt = 0,v = 0,l = strlen(s),i;
	char c[100001];
	for(i=0;i<l;i++)
		v = v*n+char_to_digit(s[i]);
	while(v!=0)
		c[cnt] = digit_to_char(v%m),v /= m,cnt++;
	s[cnt] = '\0';
	for(i=cnt;i>=0;i--)
		s[cnt-i-1] = c[i];
}
void strupper(char s[])
{
	int i,l;
	l = strlen(s); 
	for(i=0;i<l;i++)
		if(islower(s[i]))
			s[i] -= 32;
}
void strlower(char s[])
{
	int i,l;
	l = strlen(s);
	for(i=0;i<l;i++)
		if(isupper(s[i]))
			s[i] += 32; 
}
int qh(int n)
{
	int s = 0,a;
	while(n)
	{
		a = n%10;
		n /= 10;
		s += a;
	}
	return s;
}
void makejc(int n,ll p)
{
	int i;
	fac[0] = 1;
	for(i=1;i<=n;i++)
		fac[i] = (fac[i-1]*i)%p;
	return;
}
ll C(ll n,ll m,ll p)
{
	if(m>n)
		return 0;
	return ((fac[n]*ksm(fac[m],p-2,p))%p*ksm(fac[n-m],p-2,p));
}
ll jc(int n,ll p)
{
	makejc(n,p);
	return fac[n];
}