闲聊帖搬来的

#pragma GCC optimize(0)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
//1.欧几里得算法(递归法)
inline long long GCD(long long x, long long y){
	if(x<y) x^=y, y^=x, x^=y;
	return y==0?x:GCD(y,x%y);
}
//1.欧几里得算法(迭代法)
inline long long _GCD_(long long x, long long y){
	if(x<y) x^=y, y^=x, x^=y;
	while(y) x^=y, y^=x, x^=y, y%=x;
	return x;
}
//2.斐波那契数列通项公式1
inline double Fibonacci_Sequence(long long n){
	double i(sqrt(5.0)), j(pow((1+i)/2,n)), k(pow((1-i)/2,n));
	return (1/i)*(j-k);
}
//2.斐波那契数列通项公式2
inline double Fibonacci_Sequence_(long long n){
	double i(sqrt(5.0)), j(pow((1+i)/2,n)), k(pow((1-i)/2,n));
	return (i/5)*(j-k);
}
//3.快速筛选素数
inline void sieve(long long n){
	const long long N(1e8+1);
	bool prime[N];
	long long primes[N];
	memset(prime,true,sizeof(prime));
	for(long long i(2); i<=n; ++i){
		if(prime[i]) primes[++primes[0]]=i;
		for(long long j(1); j<=primes[0] && i*primes[j]<=n; ++j){
		    prime[i*primes[j]]=false; 
		    if(i%primes[j]==0) break;
		}
	}
	return;
}
//3.快速判定素数
inline long long pow(long long a, long long b, long long p){ 
	long long res(1%p);
	for(; b; b>>=1,a=a*a%p) if(b&1) res=res*a%p; 
	return res; 
}
inline bool millerRabin(long long n){
	if(n<3 || !(n&1)) return n==2; 
	long long u(n-1), t(0); 
	while(!(u&1)) u>>=1, ++t; 
	for(long long i(0); i<5; ++i){
		long long a(rand()%(n-2)+2), v(pow(a,u,n)), s(0); 
		for(; s<t; ++s, v=v*v%n) if(v==n-1 || v==1) break;
		if(s==t) return false; 
	} 
	return true; 
}
//4.分解质因数
inline void primeFactors(long long n){
    while((n&1)==0){
        cout << 2 << ' ';
        n>>=1;
    }
    for(long long i(3); i*i<=n; i+=2){
        while(n%i==0){
            cout << i << ' ';
            n/=i;
        }
    }
    if(n>2) cout << n;
    return;
}
//5.求圆周率pi的精确值
inline double pi(long long n=100, long long ans=0, long long x=1.0/sqrt(3.0)){
	long long a(n), b(n);
	if(a%4==3) a-=2;
	if(b%4==1) b-=2;	
	while(a>0) ans+=pow(x,a)/a, a-=4;
	while(b>0) ans-=pow(x,b)/b, b-=4;
	return 6*ans;	
}
//6.龟速乘+快速幂
inline long long multi(long long a, long long b, long long m){
	long long ans(0);
	a%=m;
	while(b){
		if(b&1) ans=(ans+a)%m, b--;
		b>>=1, a=2*a%m;
	}
	return ans;
}
inline long long quick_mod(long long a, long long b, long long m){
	long long ans(1);
	a%=m;
	while(b){
		if(b&1) ans=multi(ans,a,m), b--;
		b>>=1, a=multi(a,a,m);
	}
	return ans;
} 
//7.二分查找(向左寻找)
inline long long left_search(long long l, long long r, long long target, long long a[]){
	while(l<r){
		long long mid((l+r)>>1);
		if(a[mid]<target) l=mid+1;
		else r=mid;
	}
	if(a[l]==target) return l;
	return -1;
}
//7.二分查找(向右寻找)
inline long long right_search(long long l, long long r, long long target, long long a[]){
	while(l<r){
		long long mid((l+r+1)>>1);
		if(a[mid]<=target) l=mid;
		else r=mid-1;
	}
	if(a[l]==target) return l;
	return -1;
}
//8.排序
inline void selection_sort(long long a[], long long n){
	for(long long i(1); i<n; ++i){
		long long pos(i);
		for(long long j(i+1); j<=n; ++j){
			if(a[j]<a[i]) pos=j;
		}
		a[i]^=a[pos], a[pos]^=a[i], a[i]^=a[pos];
	}
}
//8.排序
inline void insertion_sort(long long a[], long long n){
	for(long long i(2); i<=n; ++i){
		long long j(i-1);
		while(j>=1 && a[j]>a[i]) a[j+1]=a[j], --j;
		a[j+1]=a[i];
	}
	return;
}
//8.排序
inline void bubble_sort(long long a[], long long n){
	for(long long i(1); i<n; ++i){
		bool flag(true);
		for(long long j(1); j<=n-i; ++j){
			if(a[j]<a[j-1]) a[j]^=a[j-1], a[j-1]^=a[j], a[j]^=a[j-1], flag=false;
		}
		if(flag) break;
	}
	return;
}
//8.排序
inline void quick_sort(long long a[], long long l, long long r){
	if(l>=r) return;
	long long i(l), j(r), temp(a[l]);
	while(i<j){
		while(i<j && a[j]>=temp) --j;
		a[i]=a[j];
		while(i<j && a[i]<=temp) ++i;
		a[j]=a[i];
	}
	a[i]=temp;
	quick_sort(a,l,i-1);
	quick_sort(a,i+1,r);
	return;
}
//8.排序
inline void count_sort(long long a[], long long n){
	const long long N(1e7+1);
	long long cnt[N], ans[N], maxn(0), minn(INT_MAX);
	for(long long i(1); i<=n; ++i) maxn=max(maxn,a[i]), minn=min(minn,a[i]);
	for(long long i(1); i<=n; ++i) cnt[a[i]-minn]++;
	for(long long i(1); i<maxn-minn+1; ++i) cnt[i]+=cnt[i-1];
	for(long long i(n); i>0; --i) ans[cnt[a[i]-minn]]=a[i], cnt[a[i]-minn]--;
	return;
}
//8.排序
inline void merge_sort(long long a[], long long temp[], long long l, long long r){
	if(r-l<=1) return;
	long long mid((l+r)>>1);
	merge_sort(a,temp,l,mid);
	merge_sort(a,temp,mid,r);
	long long p(l), q(mid), s(l);
	while(s<r){
		if(p>=mid || (q<r && a[p]>a[q])) temp[s++]=a[q++];
		else temp[s++]=a[p++];
	} 
	for(long long i(l); i<r; ++i) a[i]=temp[i];
	return;
}
//8.排序
inline void queue_radix_sort(long long a[], long long n){
	queue<long long> que[2];
	long long expe(1);
    for(long long ind(1);ind<=31;++ind){
        bool flag(true);
        for(long long i(1);i<=n;++i){
            if(expe<=a[i]) flag=false;
            que[bool(a[i]&expe)].push(a[i]);
        }
        long long cnt(0);
        for(long long i(0);i<=1;++i){
            while(que[i].size()){
                a[++cnt]=que[i].front();
                que[i].pop();
            }
        }
        if(flag) return;
        expe<<=1;
    }
    return;
} 
//8.排序
inline void radix_sort(long long n, long long a[]){
	long long *b(new long long[n]), *cnt(new long long[1<<8]), mask((1<<8)-1), *x=a, *y=b;
	for(long long i(0);i<32;i+=8){
		for(long long j(0);j!=(1<<8);++j) cnt[j]=0;
		for(long long j(0);j<n;++j) ++cnt[x[j]>>i&mask];
		for(long long sum(0), j(0);j<(1<<8);++j) sum+=cnt[j], cnt[j]=sum-cnt[j];
		for(long long j(0);j<n;++j) y[cnt[x[j]>>i&mask]++]=x[j];
		swap(x,y); 
	}
	delete[] cnt, b;
	return;
} 
//8.排序
inline void shell_sort(long long array[], long long length){
  	long long h(1);
  	while(h<length/3) h=3*h+1;
	while(h>=1){
	    for(long long i(h);i<length;++i){
		    for(long long j(i);j>=h && array[j]<array[j-h];j-=h){
		    	array[j]^=array[j-h], array[j]^=array[j-h], array[j]^=array[j-h];
		    }
	    }
	    h/=3;
	}
}
//8.排序
long long temp[100000000];
inline long long winner(long long pos1, long long pos2, long long n){
	long long u=pos1>=n?pos1:temp[pos1], v=pos2>=n?pos2:temp[pos2];
	if(temp[u]<=temp[v]) return u;
	return v;
}
inline long long creat_tree(long long &value, long long a[], long long n){
    for(long long i(0);i<n;i++) temp[n+i]=a[i];
    for(long long i(2*n-1);i>1;i-=2) temp[i/2]=winner(i/2,i-1,n);
    value=temp[temp[1]], temp[temp[1]]=INT_MAX;
    return value;
}
inline void recreat(long long &value, long long n){
	long long i=temp[1];
	while(i>1){
	    if(i%2==0 && i<2*n-1) temp[i/2]=winner(i,i+1,n);
	    else temp[i/2]=winner(i,i-1,n);
	    i>>1;
	}
	value=temp[temp[1]], temp[temp[1]]=INT_MAX;
	return;
}
inline void tournament_sort(long long a[], long long n){
	long long value=creat_tree(value,a,n);
	for(long long i(0);i<n;i++){
	    a[i]=value;
	    recreat(value,n);
	}
	return;
}
//9.欧拉函数判定
inline long long phi(long long n=1e18+1){
	long long ans(n);
	for(long long i(2);i*i<=n;++i){
		if(n%i==0){
	        ans=ans/i*(i-1);
	        while(n%i==0) n/=i;
	    }
	}
	if(n>1) ans=ans/n*(n-1);
	return ans;
} 
//9.欧拉函数筛选
inline void getphi(long long n=5e7+1){
	long long phi[n], prime[n], tot;
	bool mark[n];
	phi[1]=1;
	for(long long i(2);i<=n;++i){
		if(!mark[i]) prime[++tot]=i, phi[i]=i-1;
		for(long long j(1);j<=tot;++j){
			if(i*prime[j]>n) break;
			mark[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else{
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
	}
	for(long long i(1);i<=n;++i) phi[i]=phi[i]*2+1; 
	return;
}
//10.乘法逆元判定
inline long long kapok(long long a, long long m, long long p){
	long long ret(1);
	while(m){
		if(m&1) ret*=a, ret%=p;
		a=a*a%p, m>>=1;
	}
	return (p+ret%p)%p;
}
inline void decide(long long n, long long p){
	const long long N(1e8+1);
	long long inverse[N];  
	for(long long i(1);i<=n;++i) inverse[i]=kapok(i,p-2,p);
	return;
}
//10.乘法逆元筛法
inline void inverse_element(long long a, long long p){
	const long long N(1e8+1);
	long long inverse[N];
	inverse[0]=0, inverse[1]=1;
	for(long long i(2);i<=a;++i) inverse[i]=((p-p/i)*inverse[p%i])%p;
	return;
}
//11.KMP算法
inline vector<long long> getPrefixTable(const string& pattern){
    long long m(pattern.size()), k(0);
    vector<long long> prefix(m,0);
    for(long long q(1); q<m; prefix[q++]=k){
        while(k>0 && pattern[k]!=pattern[q]) k=prefix[k-1];
        if(pattern[k]==pattern[q]) ++k;
    }
    return prefix;
}
inline long long KMPsearch(const string& text, const string& pattern){
    long long n(text.size()), m(pattern.size());
    vector<long long> prefix(getPrefixTable(pattern));
    long long q(0), count(0);
    for (long long i(0); i<n; ++i){
        while(q>0 && pattern[q]!=text[i]) q=prefix[q-1];
        if(pattern[q]==text[i]) ++q;
        if(q==m) ++count, q=prefix[q-1];
    }
    return count;
}