缺省源求品鉴

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int mod=1e9+7;
int n,m;
void Max(int &a,int b){a>=b?0:a=b;}
void Min(int &a,int b){a<=b?0:a=b;}
int lowbit(int x){return x&(-x);}
int qpow(int a,int b){
	int ans=1;
	while(b>0){
		if(b&1){
			ans*=a;
			ans%=mod;
		}
		a*=a;
		a%=mod;
		b/=2;
	}
	return ans;
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(int x){
    if(x<0){
        putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}

namespace seg_tree{
	void pushup(int rt);
	void build(int rt,int l,int r);
	void modify(int rt,int v);
	void pushdown(int rt);
	void update(int rt,int l,int r,int v);
	int query(int rt,int l,int r);
}
namespace dij_sp{
	void init();
	void dijstra(int s);
}
namespace fa_sp{
	void init();
	bool spfa(int s);
}
namespace fen_tree{
	void update(int rt,int v);
	int query(int rt);
}
namespace lca{
	void dfs(int id,int fa);
	int lca(int a,int b);
}
namespace st{
	void init();
	int query(int rt);
}
namespace dsu{
	void init();
	int find(int id);
}
namespace mst{
	void init();
	int mst();
}
namespace exgcd{
	void exgcd(int a,int b,int &x,int &y);
	int inv(int a,int m);
}
namespace lininv{
	void init();
}
namespace linsieve{
	void pre();
}
namespace discr{
	void init();
	int get(int x);
}
namespace comb{
	void init();
	int c(int n,int m);
}
namespace crt{
	int query();
}
namespace bs{
	void init();
	bool check(int mid);
	int search(int l,int r,int goal);
}
namespace sol{
	void solve();
}

namespace seg_tree{
	int w[N];
	struct TreeNode{
		int l,r;
		int sum;
		int tag;
	}t[N<<2];
//	TreeNode operator + (TreeNode &A,TreeNode &B){
//		TreeNode C;
//		C.l=A.l;
//		C.r=B.r;
//		C.sum=A.sum+B.sum;
//		return C;
//	}
	void pushup(int rt){
		t[rt].sum=t[(rt<<1)].sum+t[(rt<<1)+1].sum;
		return;
	}
	void build(int rt,int l,int r){
		t[rt].l=l,t[rt].r=r;
		t[rt].tag=0;
		if(l==r){
			t[rt].sum=w[l];
			return;
		}
		int mid=(l+r)/2;
		build((rt<<1),l,mid);
		build((rt<<1)+1,mid+1,r);
		pushup(rt);
		return;
	}
	void modify(int rt,int v){
		t[rt].tag+=v;
		t[rt].sum+=v*(t[rt].r-t[rt].l+1);
		return;
	}
	void pushdown(int rt){
		modify(rt<<1,t[rt].tag);
		modify((rt<<1)+1,t[rt].tag);
		t[rt].tag=0;
		return;
	}
	void update(int rt,int l,int r,int v){
		if(l<=t[rt].l && t[rt].r<=r){
			modify(rt,v);
			return;
		}
		pushdown(rt);
		int mid=(t[rt].l+t[rt].r)/2;
		if(l<=mid)update((rt<<1),l,r,v);
		if(r>mid)update((rt<<1)+1,l,r,v);
		pushup(rt);
		return;
	}
	int query(int rt,int l,int r){
		if(l<=t[rt].l && t[rt].r<=r){
			return t[rt].sum;
		}
		pushdown(rt);
		int mid=(t[rt].l+t[rt].r)/2;
		int cnt=0;
		if(l<=mid)cnt+=query(rt<<1,l,r);
		if(r>mid)cnt+=query((rt<<1)+1,l,r);
		return cnt;
	}
}
namespace dij_sp{
	struct EdgeNode{
		int v;
		int w;
	};
	bool operator < (const EdgeNode &A,const EdgeNode &B){
		return A.w>B.w;
	}
	priority_queue<EdgeNode>q;
	vector<EdgeNode>e[N];
	int dis[N];
	void init(int s){
		for(int i=0;i<N;i++)dis[i]=LLONG_MAX;
		dis[s]=0;
	}
	void dijstra(int s){
		q.push({s,0});
		while(!q.empty()){
			int id=(q.top()).v;
			int w=(q.top()).w;
			q.pop();
			if(w>dis[id])continue;
			for(EdgeNode to:e[id]){
				int cost=w+to.w;
				if(cost<dis[to.v]){
					dis[to.v]=cost;
					q.push({to.v,cost});
				}
			}
		}
		return;
	}
}
namespace fa_sp{
	struct EdgeNode{
		int v;
		int w;
	};
	queue<int>q;
	vector<EdgeNode>e[N];
	int dis[N],len[N],in[N];
	void init(int s){
		for(int i=1;i<N;i++)dis[i]=LLONG_MAX;
		for(int i=1;i<N;i++)len[i]=0;
		for(int i=1;i<N;i++)in[i]=0;
		for(int i=1;i<N;i++)e[i].clear();
		while(!q.empty())q.pop();
		dis[s]=0;
		in[s]=1;
		return;
	}
	bool spfa(int s){
		q.push(s);
		while(!q.empty()){
			int id=q.front();
			q.pop();
			in[id]=0;
			if(len[id]>n)return 1;
			for(EdgeNode to:e[id]){
				int cost=dis[id]+to.w;
				if(cost>=dis[to.v])continue;
				len[to.v]=len[id]+1;
				dis[to.v]=cost;
				if(!in[to.v]){
					in[to.v]=1;
					q.push(to.v);
				}
			}
		}
		return 0;
	}
}
//namespace flo_sp{
//	int dis[N][N];
//	void init(){
//		for(int i=0;i<N;i++){
//			for(int j=0;j<N;j++){
//				dis[i][j]=1e18;
//			}
//		}
//		for(int i=0;i<N;i++)dis[i][i]=0;
//	}
//	void Floyd(){
//		for(int k=1;k<=n;k++){
//			for(int i=1;i<=n;i++){
//				for(int j=1;j<=n;j++){
//					Min(dis[i][j],dis[i][k]+dis[k][j]);
//				}
//			}
//		}
//		return;
//	}
//}
namespace fen_tree{
	int t[N<<1];
	void update(int rt,int v){
		for(int i=rt;i<N;i+=lowbit(i)){
			t[i]+=v;
		}
		return;
	}
	int query(int rt){
		int ans=0;
		for(int i=rt;i>=1;i-=lowbit(i)){
			ans+=t[i];
		}
		return ans;
	}
}
namespace lca{
	int st[21][N];
	int deep[N];
	vector<int>e[N];
	void dfs(int id,int fa){
		st[0][id]=fa;
		deep[id]=deep[fa]+1;
		for(int i=1;i<=20;i++){
			st[i][id]=st[i-1][st[i-1][id]];
		}
		for(int to:e[id]){
			if(to==fa)continue;
			dfs(to,id);
		}
		return;
	}
	int lca(int a,int b){
		if(deep[a]<deep[b])swap(a,b);
		int diff=deep[a]-deep[b];
		for(int i=20;i>=0;i--){
			if(diff&(1<<i)){
				a=st[i][a];
			}
		}
		if(a==b)return a;
		for(int i=20;i>=0;i--){
			if(st[i][a]!=st[i][b]){
				a=st[i][a];
				b=st[i][b];
			}
		}
		a=st[0][a];
		return a;
	}
}
namespace st{
	int a[N];
	int st[21][N];
	void init(){
		for(int i=1;i<=n;i++)st[0][i]=a[i];
		for(int i=1;i<=20;i++){
			for(int j=1;j<=n-(1<<i)+1;j++){
				st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
			}
		}
		return;
	}
	int query(int l,int r){
		int diff=r-l+1;
		int lg=log2(diff);
		return max(st[lg][l],st[lg][r-(1<<lg)+1]);
	}
}
namespace dsu{
	int fa[N];
	void init(){
		for(int i=0;i<N;i++)fa[i]=i;
		return;
	}
	int find(int id){
		return id==fa[id]?id:fa[id]=find(fa[id]);
	}
}
namespace mst{
	struct EdgeNode{
		int u,v,w;
	};
	EdgeNode e[N];
	vector<EdgeNode>v;
	int ans=0;
	int cnt=0;
	void init(){
		ans=0;
		cnt=0;
		dsu::init();
	}
	bool cmp(EdgeNode A,EdgeNode B){
		return A.w<B.w;
	}
	int mst(){
		sort(e+1,e+m+1,cmp);
		for(int i=1;i<=m;i++){
			int fu=dsu::find(e[i].u);
			int fv=dsu::find(e[i].v);
			if(fu!=fv){
				dsu::fa[fu]=fv;
				v.push_back({e[i].u,e[i].v,e[i].w});
				ans+=e[i].w;
				cnt++;
			}
		}
		return ans;
	}
}
namespace exgcd{
	void exgcd(int a,int b,int &x, int &y) {
	  if(!b){
	    x=1;
	    y=0;
	  } else {
	    exgcd(b,a%b,y,x);
	    y-=a/b*x;
	  }
	}
	int inv(int a,int m) {
	  int x,y;
	  exgcd(a,m,x,y);
	  return ((x%m)+m)%m;
	}
}
namespace lininv{
	int inv[N];
	void init(){
		inv[1]=1;
		for (int i=2;i<N;i++) {
		    inv[i]=(mod-mod/i)*inv[mod%i];
		    inv[i]%=mod;
		}
		return;
	}
}
namespace linsieve{
	bool notprime[N];
	vector<int>pri;
	void pre(){
		notprime[1]=1;
		for (int i = 2; i <= n; ++i) {
	    if (!notprime[i]) {
	      pri.push_back(i);
	    }
	    for (int prij:pri) {
	      if (i*prij>n)break;
	      notprime[i*prij]=1;
	      if (i%prij==0)break;
	    }
	  }
	}
}
namespace discr{
	vector<int>v;
	void init(){
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
	}
	int get(int x){
		return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
	}
}
namespace comb{
	int fac[N];
	void init(){
		fac[0]=1;
		for(int i=1;i<N;i++)fac[i]=(fac[i-1]*i)%mod;
		lininv::init();
		return;
	}
	int c(int n,int m) {
        if (n<m || m<0) return 0;
        return (((fac[n]*(lininv::inv[m]))%mod)*(lininv::inv[n-m]))%mod;
    }
}
namespace crt{
	int a[N],b[N];
	int query(){
		int M=1;
		for(int i=1;i<=n;i++)M*=b[i];
		int ans=0;
		for(int i=1;i<=n;i++){
			int p=M/b[i];
			int inv=exgcd::inv(p,b[i]);
			ans+=(((inv*p)%M)*a[i])%M;
			ans%=M;
		}
		ans=(ans%M+M)%M;
		return ans;
	}
}
namespace bs{
	int a[N];
	void init(){
		
	}
	bool check(int mid){
		
	}
	int search(int l,int r,int goal=0){
		int L=l,R=r,best=-1;
		while(L<=R){
			int mid=(L+R)/2;
			if(check(mid)){
				R=mid-1;
				best=mid;
			}
			else{
				L=mid+1;
			}
		}
		return best;
	}
}
namespace sol{
	void solve(){
		
	}
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	sol::solve();
	return 0;
}