ll qmul(ll x,ll y,ll mod)
{
	ll ans=0;
	while(y)
	{
		if(y&1) (ans+=x)%=mod;
		y>>=1;
		(x+=x)%=mod;
	}
	return ans;
}

ll qpow(ll x,ll y,ll mod)
{
	ll ans=1;
	while(y)
	{
		if(y&1) (ans*=x)%=mod;
		y>>=1;
		(x*=x)%=mod;
	}
	return ans;
}

ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}

void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b) exgcd(b,a%b,y,x),y-=a/b*x;
	else x=1,y=0;
}

void init()
{
	f[0]=v[0]=1; for(int i=1;i<=mod;i++) f[i]=f[i-1]*i%mod;
	v[mod-1]=mod-1; for(int i=mod-2;i;i--) v[i]=v[i+1]*(i+1)%mod;
}
ll lucas(ll a,ll b)
{
    if(a<b)
        return 0;
    if(a<mod&&b<mod)
        return 1ll*f[a]*v[b]%mod*v[a-b]%mod;
    return 1ll*lucas(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;
}

ll num(ll x,ll p)
{
	ll re=0;
	while(x)
	{
		re+=x/p;
		x/=p;
	}
	return re;
}
ll fac(ll n,ll p,ll pc)
{
	if(!n) return 1ll;
	ll sum=1ll;
	for(int i=1;i<pc;i++) if(i%p) (sum*=i)%=pc;
	ll ans=qpow(sum,n/pc,pc);
	for(int i=1;i<=n%pc;i++) if(i%p) (ans*=i)%=pc;
	return ans*fac(n/p,p,pc)%pc;
}
ll inv(ll n,ll p)
{
	ll x,y;
	exgcd(n,p,x,y);
	((x%=p)+=p)%=p;
	return x;
}
ll C(ll x,ll y,ll p,ll pc)
{
	if(x<y) return 0ll;
	int cnt=num(x,p)-num(y,p)-num(x-y,p);
	return fac(x,p,pc)*inv(fac(y,p,pc),pc)%pc*inv(fac(x-y,p,pc),pc)%pc*qpow(p,cnt,pc)%pc;
}

map<ll,ll>MP;
ll bsgs(ll A,ll B,ll C) // x^A \equiv B (mod\ C)
{
	ll m=ceil(sqrt(C+0.5));
	MP.clear();
	ll now=1;
	for(int i=1;i<=m;i++)
	{
		(now*=A)%=C;
		if(!MP[now]) MP[now]=i;
	}
	A=qpow(A,m,C);
	now=1;
	for(int i=0;i<=m;i++)
	{
		ll x,y;
		exgcd(now,C,x,y);
		x=(x*B%C+C)%C;
		if(MP.count(x)) return i*m+MP[x];
		(now*=A)%=C;
	}
	return 0;
}

ll get_ori(ll p,ll phi)
{
	int c=0;
	for(int i=2;1ll*i*i<=phi;i++) if(phi%i==0)
	{
		f[++c]=i; f[++c]=phi/i;
	}
	for(int g=2;;g++)
	{
		int j;
		for(j=1;j<=c;j++) if(qpow(g,f[j],p)==1) break;
		if(j==c+1) return g;
	}
	return 0;
}

for(i=1<<30;i;i>>=1)
{
	for(j=1;j<=n;j++) if(!vis[j]&&a[j].v&i) break;
	if(j>n) continue;
	sum-=a[j].num; vis[j]=true;
	for(k=1;k<=n;k++) if(!vis[k]&&a[k].v&i) a[k].v^=a[j].v;
}

void tarjan(int p)
{
	st[++top]=p; ins[p]=true;
	dep[p]=low[p]=++cnt;
	for(int i=head[p];i;i=nxt[i])
	{
		if(!dep[to[i]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
		else if(ins[to[i]]) low[p]=min(low[p],dep[to[i]]);
	}
	if(dep[p]==low[p])
	{
		Number++;
		int t;
		do
		{
			t=st[top--]; ins[t]=false;
			f[Number][++f[Number][0]]=t;
		}while(t!=p);
	}
}

priority_queue<pair<int,int> >q;
void Dijkstra()
{
	while(!q.empty()) q.pop();
	memset(dis,0x3f,sizeof dis); dis[S]=0; q.push(mp(0,S));
	while(!q.empty())
	{
		while(!q.empty()&&-q.top().first>dis[q.top().second]) q.pop();
		if(q.empty()) return;
		int x=q.top().second; q.pop();
		for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i])
		{
			dis[to[i]]=dis[x]+val[i];
			q.push(mp(-dis[to[i]],to[i]));
		}
	}
}

queue<int>q;
void spfa()
{
	while(!q.empty()) q.pop();
	memset(dis,0x3f,sizeof dis); dis[S]=0; q.push(S);
	vis[x]=true;
	while(!q.empty())
	{
		int x=q.front(); q.pop(); vis[x]=false;
		for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i])
		{
			dis[to[i]]=dis[x]+val[i];
			if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=true;
		}
	}
}

void dfs(int p, int fa) {
    f[0][p] = fa;
    dep[p] = dep[fa] + 1;
    for (int i = 1; i <= 20; i ++ )
        f[i][p] = f[i-1][f[i-1][p]];
    for (int i = head[p]; i; i = nxt[i]) {
        if(to[i] != fa) {
            dfs(to[i], p);
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; ~i; i -- ) {
        if (dep[f[i][x]] >= dep[y]) {
            x = f[i][x];
        }
    }
    if (x == y) return x;
    for (int i = 20; ~i; i -- ) {
        if (f[i][x] != f[i][y]) {
            x = f[i][x];
            y = f[i][y];
        }
    }
    return f[0][x];
}

int merge(int x, int y) {
    if (!x || !y) return x | y;
    pushdown(x); pushdown(y);
    if (a[x].key > a[y].key) {
        a[x].rs = merge(a[x].rs, y);
        pushup(x);
        return x;
    }
    else {
        a[y].ls = merge(x, a[y].ls);
        pushup(y);
        return y;
    }
}

par split(int x, int k) {
    if(!k)
        return (par) {0, x};
    pushdown(x);
    int ls = a[x].ls, rs = a[x].rs;
    if (k == a[ls].size) {
        a[x].ls = 0;
        pushup(x);
        return (par) {ls, x};
    }
    else if (k == a[ls].size + 1) {
        a[x].rs = 0;
        pushup(x);
        return (par) {x, rs};
    }
    else if (k < a[ls].size) {
        par t = split(ls, k);
        a[x].ls = t.y;
        pushup(x);
        return (par) {t.x, x};
    }
    else {
        par t = split(rs, k - a[ls].size - 1);
        a[x].rs = t.x;
        pushup(x);
        return (par) {x, t.y};
    }
}