弱智吧

#include<bits/stdc++.h>
// #define int long long
#define N (2)
#define I i
#define J j
#define raed read
#define reaD read
#define reAD read
#define rEAD read
#define READ read
#define REAd read
#define REad read
#define Read read
#define Reda read
#define redA read
#define reDA read
#define redA read
#define itn signed
#define Itn signed
#define ITN signed
#define Int signed
#define INT signed
#define foR for
#define fot for
#define foT for
#define sort stable_sort
#define REG register 
using namespace std;
namespace IO
{
    #define ll signed
    const int MAX=1<<24;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(IO::p1==IO::p2&&(IO::p2=(IO::p1=IO::buf)+fread(IO::buf,1,1<<24,stdin),IO::p1==IO::p2)?EOF:*IO::p1++)
    /*
    template<typename T>
    inline void read(T)
    {

    }
    */
    inline int read()//int
    {
        register int x(0);register bool f(true);
        register char c(gc());
        for(;c<48||c>57;c=gc())if(c=='-')f=false;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    inline double dead()//double
    {
        register double x(0);register bool f(true);
        register int lee(0);register char c(gc());
        for(;c<48||c>57;c=gc())if(c=='-')f=false;
        for(;c>=48&&c<=57;c=gc())x=x*10+(c^48);
        if(c=='.')
        {
            c=gc();
            for(;c>=48&&c<=57;c=gc())x=(x*10.0+(c^48)),++lee;
            x/=pow(10,lee);
        }
        return f?x:-x;
    }
    inline double sead()//小于18位
    {
        register double x(0);register bool f(true);
        register long long d(0);register int lee(0);
        register char c(gc());
        for(;c<48||c>57;c=gc())if(c=='-')f=false;
        for(;c>=48&&c<=57;c=gc())d=(d<<3)+(d<<1)+(c^48);
        if(c=='.')
        {
            c=gc();
            for(;c>=48&&c<=57;c=gc())d=(d<<3)+(d<<1)+(c^48),++lee;
            x=1.0*d/pow(10,lee);
        }
        else return d;
        return f?x:-x;
    }
    inline void cead(string &s)
    {
        s.clear();
        register char c(gc());
        for(;c==' '||c=='\n';c=gc());
        for(;c!=' '&&c!='\n'&&c!=EOF;c=gc())s+=c;
        return;
    }
    inline string quead()
    {
        string s;
        register char c(gc());
        for(;c==' '||c=='\n';c=gc());
        for(;c!=' '&&c!='\n'&&c!=EOF;c=gc())s+=c;
        return s;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char ed){pit(x);*o++=ed;}
    void putstr(string s,char ed){for(char y:s)*o++=y;*o++=ed;}
    void putc(char ed){*o++=ed;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;
using IO::dead;using IO::sead;using IO::cead;
using IO::putstr;using IO::putc;using IO::quead;
inline signed min(signed x,signed y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline signed max(signed x,signed y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline long long min(long long x,long long y){return y&((y-x)>>63)|x&(~(y-x)>>63);}
inline long long max(long long x,long long y){return x&((y-x)>>63)|y&(~(y-x)>>63);}
inline void swap(int &x,int &y){x^=y^=x^=y;}
int n,m,k;
const double PI(acos(-1.0));
void init_set()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
/*
namespace hs
{
    int hs[N],to[N],nxt[N];
    int mod=98317,head[N],cnmhs;
    void clean(){memset(head,0,sizeof(head));}
    void add(int x,int P=mod)
    {
        hs[++cnmhs]=x,to[cnmhs]=P,x%=mod,
        nxt[cnmhs]=head[x],head[x]=cnmhs;
    }
    int find_x(int x)
    {
        for(int i(head[x%mod]);i;i=nxt[i])
            if(hs[i]==x)return to[i];
        return -1;
    }
}
namespace math
{
    int t,P,q,d;
    int x,y,k,ans,possible,lon;
    int mod[N],a[N],gt[N],nth_mod[N];
    int len,prime[700010],phi[N];//线性筛欧拉函数
    short mu[N];
    int mtot;
    bitset<N>vis;
    int jc[N],cp[N];
    long long inv[N];//乘法逆元
    long long qpow(long long x,int b,int P=P)
    {
        long long ans=1;
        for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
        return ans;
    }//O(log(b))
    int gcd(int a,int b){return b?gcd(b,a%b):a;}
    int exgcd(int a,int b,int &x,int &y)
    {
        if(!b){x=1,y=0;return a;}
        int d=exgcd(b,a%b,y,x);
        y-=(a/b*x);
        return d;
    }//O(max(a,b))
    int ola(int n)
    {
        int ans=n;
        for(int i=2;i*i<=n;++i)
        {
            if(n%i==0)ans=ans/i*(i-1);
            for(;n%i==0;n/=i);
        }
        if(n>1)ans=ans/n*(n-1);
        return ans;
    }//O(sqrt(n))
    void eular(int n)//欧拉筛
    {
        //memset(vis,0,sizeof(vis));
        phi[1]=1;
        for(int i(2);i<=n;++i)
        {
            if(!vis[i])
                prime[++len]=i,phi[i]=(i-1);
            for(int j(1);j<=len&&i*prime[j]<=n;++j)
            {
                vis[i*prime[j]]=1;
                if(!(i%prime[j]))
                    {phi[i*prime[j]]=(phi[i]*prime[j]);break;}
                else phi[i*prime[j]]=(phi[i]*(prime[j]-1));
            }
        }
    }//O(n)
    void mobius(int n)
    {
        //memset(vis,0,sizeof(vis));
        mu[1]=1;
        for(int i(2);i<=n;++i)
        {
            if(!vis[i])prime[++mtot]=i,mu[i]=-1;
            for(int j(1);j<=mtot&&i*prime[j]<=n;++j)
            {
                vis[i*prime[j]]=1;
                if(!(i%prime[j])){mu[i*prime[j]]=0;break;}
                mu[i*prime[j]]=~mu[i]+1;
            }
        }
    }//O(n)
    void eular_mobius(int n)
    {
        //memset(vis,0,sizeof(vis));
        mu[1]=phi[1]=1;
        for(int i(2);i<=n;++i)
        {
            if(!vis[i])prime[++len]=i,phi[i]=(i-1),mu[i]=-1;
            for(int j(1);j<=len&&i*prime[j]<=n;++j)
            {
                vis[i*prime[j]]=1;
                if(!(i%prime[j]))
                {
                    phi[i*prime[j]]=(phi[i]*prime[j]);
                    mu[i*prime[j]]=0;
                    break;
                }
                phi[i*prime[j]]=(phi[i]*(prime[j]-1));
                mu[i*prime[j]]=~mu[i]+1;
            }
        }
    }
    void niyuan1(int n,int P=P)//乘法逆元
    {
        inv[1]=1;
        for(int i(2);i<=n;++i)inv[i]=((P-P/i)*inv[P%i])%P;
    }//O(n)
    int inv_it(int a,int P=P)//O(log(a))
    {
        int d(exgcd(a,P,x,y));
        return(x%P+P)%P;
    }
    int C(int n,int m,int P=P)
    {
        if(m>n)return 0;
        int a(1),b(1);
        for(int i(n-m+1);i<=n;++i)a=(a*i)%P;
        for(int i(2);i<=m;++i)b=(b*i)%P;
        return(a*qpow(b,P-2,P))%P;
    }
    int jc_C(int n,int m,int P=P)
    {
        return ((jc[n])*inv_it(jc[m])%P*inv_it(jc[n-m]))%P;
    }
    int lucas(int n,int m,int P=P)
    {return(!m)?1:(C(n%P,m%P,P)*lucas(n/P,m/P,P))%P;}
    int excrt(int n)//扩展中国剩余定理
    {
        int mul(mod[1]);ans=a[1];
        int x,y,c,d;
        for(int i(2);i<=n;++i)
        {
            x=y=0;
            c=(a[i]-ans%mod[i]+mod[i])%mod[i];
            d=exgcd(mul,mod[i],x,y);
            if(!(c%d))
                ans+=(((x+mod[i])%mod[i])*(c/d)%mod[i])*mul,
                mul=mul*mod[i]/gcd(mul,mod[i]),
                ans%=mul;
            else return -1;
        }
        return ans%mul;
    }
    int exlucas_jc(int n,int mod,int P=P)
    {
        if(!n)return 1;
        int res(1);
        for(int i(1);i<=P;++i)//不含因子mod[now]
            if(i%mod)res=(res*i)%P;
        res=qpow(res,n/P,P);
        for(int i(1);i<=n%P;++i)if(i%mod)res=(res*i)%P;
        return(res*(exlucas_jc(n/mod,mod,P)))%P;
    }
    int cal(int n,int m,int mod,int P=P)
    {
        int c1(exlucas_jc(n,mod,P));
        int c2(exlucas_jc(m,mod,P));
        int c3(exlucas_jc(n-m,mod,P));
        int cnt(0);
        for(int i(n);i;i/=mod)cnt+=(i/mod);
        for(int i(m);i;i/=mod)cnt-=(i/mod);
        for(int i(n-m);i;i/=mod)cnt-=(i/mod);
        return(((qpow(mod,cnt,P)*c1)%P*inv_it(c2,P))%P*inv_it(c3,P))%P;
    }
    inline int crt(int x,int mod,int P)
    {
        return inv_it(P/mod,mod)*(P/mod)*x;
    }
    int exlucas(int n,int m,int now,int P)
    {return(crt(cal(n,m,nth_mod[now],mod[now]),mod[now],P));}
    int bsgs(int x,int y,int P=P)
    {
        if(!(x%P))return -1;
        x%=P,y%=P;
        if(y==1)return 0;
        int Z(sqrt(P)+1);
        int xx(y),yy;
        hs::clean();
        for(int i(0);i<Z;++i,xx=(xx*x)%P)hs::add(xx,i);
        yy=qpow(x,Z),xx=1;
        for(int i(1),k;i<=Z;++i)
        {
            xx=(xx*yy)%P,k=hs::find_x(xx);
            if(k!=-1)return i*Z-k;
        }
        return -1;
    }
    void error_sort(int n)
    {for(int i(2);i<=n;++i)cp[i]=(i*cp[i-1]+((i&1)?-1:1))%P;}
    void jc_set(int n)
    {jc[0]=jc[1]=1;for(int i(2);i<=n;++i)jc[i]=(jc[i-1]*i)%P;}
}
namespace kill_tree
{
    #define ls (p<<1)
    #define rs (p<<1|1)
	vector<int>e[N];
	struct tt
	{
		int l,r;
		long long add,sum,min;
	}tr[N<<2];
	int rt,r,cnt,head[N],f[N],d[N],root,b[N];
	int siz[N],son[N],rk[N],top[N],dfn[N],cnm,a[N];
	int pd[N];
	void dfs1(int x,int fa)
    {
        d[x]=d[fa]+1;
        f[x]=fa;
        siz[x]=1;
        for(int y:e[x])
        {
            if(y==fa)continue;
            dfs1(y,x);
            siz[x]+=siz[y];
            if(siz[y]>siz[son[x]])son[x]=y;
        }
    }
    void dfs2(int x,int t)
    {
        top[x]=t;
        dfn[x]=++cnt;
        rk[cnt]=x;
        b[cnt]=a[x];
        if(!son[x])return;
        dfs2(son[x],t);
        for(int y:e[x])
            if(y!=f[x]&&y!=son[x])
                dfs2(y,y);
    }
	int lca(int x,int y)
	{
		for(;top[x]!=top[y];x=f[top[x]])
			if(d[top[x]]<d[top[y]])swap(x,y);
		return d[x]>d[y]?y:x;
	}
	int find(int x,int y)
	{
		for(;top[x]!=top[y];x=f[top[x]])
		{
			if(d[top[x]]<d[top[y]])swap(x,y);
			if(d[top[x]]==y)return top[x];
		}
		return d[x]<d[y]?son[x]:son[y];
	}
	void pushup(int p)
	{
		tr[p].sum=tr[ls].sum+tr[rs].sum;
		tr[p].min=min(tr[ls].min,tr[rs].min);
	}
	void pushdown(int p)
	{
		if(tr[p].add)
			tr[ls].sum+=tr[p].add*(tr[ls].r-tr[ls].l+1),
			tr[rs].sum+=tr[p].add*(tr[rs].r-tr[rs].l+1),
			tr[ls].min+=tr[p].add,tr[rs].min+=tr[p].add,
			tr[ls].add+=tr[p].add,tr[rs].add+=tr[p].add,
			tr[p].add=0;
	}
	void build(int p,int l,int r)
	{
		tr[p].l=l,tr[p].r=r;
		if(l==r){tr[p].sum=tr[p].min=a[l];return;}
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushup(p);
	}
	void update(int p,int l,int r,long long k)
	{
		if(l<=tr[p].l&&r>=tr[p].r)
		{
			tr[p].sum+=k*(tr[p].r-tr[p].l+1);
			tr[p].min+=k;tr[p].add+=k;
			return;
		}
		int mid=(tr[p].l+tr[p].r)>>1;
		pushdown(p);
		if(l<=mid)update(ls,l,r,k);
		if(r>mid)update(rs,l,r,k);
		pushup(p);
	}
	void update_path(int p,int v,long long k)
	{
		for(;top[p]!=top[v];p=f[top[p]])
		{
			if(d[top[p]]<d[top[v]])swap(p,v);
			update(1,dfn[top[p]],dfn[p],k);
		}
		if(d[p]<d[v])swap(p,v);
		update(1,dfn[v],dfn[p],k);//最后一段
	}
	void upd(int x,int y,long long z)
	{
		int l=lca(x,y);int r=f[l];
		update(1,dfn[x],dfn[x],z),update(1,dfn[y],dfn[y],z),
		update(1,dfn[l],dfn[l],~z+1),update(1,dfn[r],dfn[r],~z+1);
	}
	void update_tree(int p,long long k){update(1,dfn[p],dfn[p]+siz[p]-1,k);}
	long long querysum(int p,int l,int r)
	{
		long long ans=0;
		if(l<=tr[p].l&&r>=tr[p].r)return tr[p].sum;
		pushdown(p);
		int mid=(tr[p].l+tr[p].r)>>1;
		while(l<=mid)ans+=querysum(ls,l,r);
		if(r>mid)ans+=querysum(rs,l,r);
		return ans;
	}
	long long querysum_path(int p,int v)
	{
		//p,v为旧点编号
		//把树链剖分成若干个重链,重链在序列中编号连续
		long long ans=0;
		for(;top[p]!=top[v];p=f[top[p]])
		{
			if(d[top[p]]<d[top[v]])swap(p,v);
			ans+=querysum(1,dfn[top[p]],dfn[p]);
		}
		if(d[p]<d[v])swap(p,v);
		ans+=querysum(1,dfn[v],dfn[p]);
		return ans;
	}
	long long querysum_tree(int x)
	{
		if(x==root)return querysum(1,1,n);
		else
			if(lca(x,root)!=x)
			return querysum(1,dfn[x],dfn[x]+siz[x]-1);
			else{int dson=find(x,root);return querysum(1,1,dfn[dson]-1),querysum(1,dfn[dson]+siz[dson],n);}
	}
	int querymin(int p,int l,int r)
	{
		int res=0x7f7f7f7f;
		if(tr[p].l>=l&&tr[p].r<=r)return tr[p].min;
		int mid=tr[p].l+tr[p].r>>1;
		while(l<=mid)res=min(res,querymin(ls,l,r));
		if(r>mid)res=min(res,querymin(rs,l,r));
		return res;
	}
    #undef ls
    #undef rs
}
namespace modui
{
    int len,ans;
    int a[N];
    int res,l,r,k;
    int out[N],cnt[N];
    struct aa{int l,r,id;}q[N];
    bool cmp(aa a,aa b)
    {return (a.r/len==b.r/len)?a.l<b.l:a.r<b.r;}
    void add(int x){ans+=(((++cnt[a[x]])<<1)-1);}
    void del(int x){ans-=((--cnt[a[x]]<<1)+1);}
    //左端点递增，每块内按照右端点排序
}
namespace MST
{
    int f[N],w;
    struct aa{int x,y,w;}e[N];
    bool cmp(aa x,aa y){return x.w<y.w;}
    int find(int x){if(x==f[x])return x;return f[x]=find(f[x]);}
    void unionf(int x,int y){x=find(x),y=find(y);f[x]=y;}
}
namespace Graph
{
    bitset<N>flag;
    int dis[N],head[N],cnt;
    struct ee{int nxt,to,w;}e[N<<1];
    void add(int u,int v,int w)
    {e[++cnt]={head[u],v,w};head[u]=cnt;}
    void spfa(int x)
    {
        int now;
        deque<int>q;
        for(int i(0);i<=n;++i)flag[i]=false;
        for(int i(0);i<=n;i++)dis[i]=100000000;
        dis[x]=0;
        q.push_back(x);
        flag[x]=true;
        for(;!q.empty();)
        {
            now=q.front();
            flag[now]=false;
            q.pop_front();
            if(!q.empty()&&dis[q.front()]>dis[q.back()])
            {
                int tmp=q.front();
                q.pop_front();
                q.push_front(q.back());
                q.pop_back();
                q.push_back(tmp);
            }
            for(int i(head[now]);i;i=e[i].nxt)
            {
                int s=e[i].to;
                if(dis[s]>dis[now]+e[i].w)
                {
                    dis[s]=dis[now]+e[i].w;
                    if(!flag[s])
                    {
                        if(!q.empty()&&dis[q.front()]>dis[q.back()])
                        {
                            int tmp=q.front();
                            q.pop_front();
                            q.push_front(q.back());
                            q.pop_back();
                            q.push_back(tmp);
                        }
                        if(!q.empty()&&dis[q.front()]<dis[s])
                        q.push_back(s),flag[s]=true;
                        else q.push_front(s),flag[s]=true;
                    }
                }
            }
        }
    }
    void dijkstra(int x)
    {
        int k;
        priority_queue<pair<int,int>>q;
        for(int i(0);i<=n;i++)dis[i]=0x3f3f3f3f;
        for(int i(0);i<=n;++i)flag[i]=false;
        dis[x]=0;
        q.push(make_pair(0,x));
        while(!q.empty())
        {
            k=q.top().second;
            q.pop();
            if(!flag[k])
            {
                flag[k]=true;
                for(int i(head[k]);i;i=e[i].nxt)
                {
                    int to=e[i].to;
                    if(dis[to]>dis[k]+e[i].w)
                    {
                        dis[to]=dis[k]+e[i].w;
                        q.push(make_pair(~dis[to]+1,to));
                    }
                }
            }
        }
    }
}
namespace _01Trie
{
    int ch[N][2],maxsiz(1<<30),cnt;
    inline void add(int val)
    {
        int rt(0);
        for(int i(maxsiz);i;i>>=1)
        {
            bool x(val&i);//查看该位是几
            if(!ch[rt][x])ch[rt][x]=++cnt;
            rt=ch[rt][x];
        }
    }
    inline int query(int val)
    {
        int ans(0),rt(0);
        for(int i(maxsiz);i;i>>=1)
        {
            bool x(val&i);//查看该位是几
            if(ch[rt][x^1])ans=ans<<1|1,rt=ch[rt][x^1];
            else ans<<=1,rt=ch[rt][x];
        }
        return ans;
    }
}
namespace Trie
{
    #define M 63
    int t[N][M],siz,ed[N];
    void init()
    {
        for(int i(0);i<=siz;++i)for(int j(0);j<=62;++j)t[i][j]=0;
        for(int i(1);i<=siz;++i)ed[i]=0;
        siz=0;
    }
    int getac(char ch)
    {
        if(ch>='a'&&ch<='z')return ch-'a';
        if(ch>='A'&&ch<='Z')return ch-'A'+26;
        if(ch>='0'&&ch<='9')return ch-'0'+52;
        return 0;
    }
    void insert(string s)
    {
        int rt(0),len(s.size());
        for(int i(0);i<len;++i)
        {
            int x(getac(s[i]));
            if(!t[rt][x])t[rt][x]=++siz;
            rt=t[rt][x];
        }
        ++ed[rt];
    }
    int find(string s)
    {
        int rt(0),len(s.size());
        for(int i(0);i<len;++i)
        {
            int x(getac(s[i]));
            if(!t[rt][x])return 0;
            rt=t[rt][x];
        }
        return ed[rt];
    }
    #undef M
}
namespace Manacher
{
    string s,t;
    int p[N];
    int manacher()
    {
        t="$#";
        for(int i(0);i<s.size();++i)
            t+=s[i],t+="#";
        int mx(0),id(0),adolf(0),hitler(0);
        for(int i(1);i<t.size();++i)
        {
            p[i]=mx>i?min(p[(id<<1)-i],mx-i):1;
            for(;t[i+p[i]]==t[i-p[i]];++p[i]);
            if(mx<i+p[i])mx=i+p[i],id=i;
            if(adolf<p[i])adolf=p[i],hitler=i;
        }
        return adolf-1;
    }
}
namespace Splay
{
    int root,tot;
    struct splay{int fa,ch[2],val,cnt,siz;}t[N];
    void update(int x)
    {
        t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
    }
    void rotate(int x)
    {
        int y(t[x].fa),z(t[y].fa),k(t[y].ch[1]==x);
        t[z].ch[t[z].ch[1]==y]=x;
        t[x].fa=z;
        t[y].ch[k]=t[x].ch[k^1];
        t[t[x].ch[k^1]].fa=y;
        t[x].ch[k^1]=y;
        t[y].fa=x;
        update(y),update(x);
    }
    void turn(int x,int king)
    {
        for(;t[x].fa!=king;)
        {
            int y(t[x].fa),z(t[y].fa);
            if(z!=king)
                (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!king)root=x;
    }
    inline void find(int x)
    {
        int u(root);
        if(!u)return;
        for(;t[u].ch[x>t[u].val]&&x!=t[u].val;u=t[u].ch[x>t[u].val]);
        turn(u,0);
    }
    inline void insert(int x)
    {
        int u(root),fa(0);
        for(;u&&t[u].val!=x;)fa=u,u=t[u].ch[x>t[u].val];
        if(u)++t[u].cnt;
        else
        {
            u=++tot;
            if(fa)t[fa].ch[x>t[fa].val]=u;
            t[u].ch[0]=t[u].ch[1];
            t[tot].fa=fa;
            t[tot].val=x;
            t[tot].cnt=1;
            t[tot].siz=1;
        }
        turn(u,0);
    }
    inline int Next(int x,bool f)//前驱(0)，后继(1)
    {
        find(x);
        int u(root);
        if((t[u].val>x&&f)||(t[u].val<x&&!f))return u;
        u=t[u].ch[f];
        for(;t[u].ch[f^1];u=t[u].ch[f^1]);
        return u;
    }
    inline void Delete(int x)
    {
        int las(Next(x,0)),nxt(Next(x,1));
        turn(las,0),turn(nxt,las);
        int del=t[nxt].ch[0];
        if(t[del].cnt>1)--t[del].cnt,turn(del,0);
        else t[nxt].ch[0]=0;
    }
    inline int Kth(int x)
    {
        int u(root);
        if(t[u].siz<x)return 0;
        for(;1;)
        {
            int y=t[u].ch[0];
            if(x>t[y].siz+t[u].cnt)
                x-=t[y].siz+t[u].cnt,u=t[u].ch[1];
            else
                if(t[y].siz>=x)u=y;
                else return t[u].val;
        }
    }
}
namespace Art_Splay
{
    struct Splay{int s[2],p,v,siz,tag;}t[2000010];
    int root,idx;
    void pushup(int x)
    {t[x].siz=t[t[x].s[0]].siz+t[t[x].s[1]].siz+1;}
    void pushdown(int x)
    {
        if(t[x].tag)
            swap(t[x].s[0],t[x].s[1]),
            t[t[x].s[0]].tag^=1,
            t[t[x].s[1]].tag^=1,
            t[x].tag=0;
    }
    void rotate(int x)
    {
        int y(t[x].p),z(t[y].p),k(t[y].s[1]==x);
        t[z].s[t[z].s[1]==y]=x;
        t[x].p=z;
        t[y].s[k]=t[x].s[k^1];
        t[t[x].s[k^1]].p=y;
        t[x].s[k^1]=y;
        t[y].p=x;
        pushup(y),pushup(x);
    }
    void turn(int x,int k)
    {
        for(;t[x].p!=k;)
        {
            int y(t[x].p),z(t[y].p);
            if(z!=k)
                (t[z].s[0]==y)^(t[y].s[0]==x)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!k)root=x;
    }
    inline void insert(int x)
    {
        int u(root),p(0);
        for(;u;)p=u,u=t[u].s[x>t[u].v];
        u=++idx;
        t[p].s[x>t[p].v]=u;
        t[idx].p=p;
        t[idx].v=x;
        t[idx].siz=1;
        turn(u,0);
    }
    inline int Kth(int x)
    {
        int u(root);
        for(;1;)
        {
            pushdown(u);
            int y=t[u].s[0];
            if(x>t[y].siz+1)
                x-=t[y].siz+1,u=t[u].s[1];
            else if(t[y].siz>=x)u=y;
            else return u;
        }
    }
    void output(int x)
    {
        pushdown(x);
        if(t[x].s[0])output(t[x].s[0]);
        if(t[x].v>=1&&t[x].v<=n)write(t[x].v,' ');
        if(t[x].s[1])output(t[x].s[1]);
    }
}

namespace BB_Splay
{
    int a[N],root[N],idx,bin[N],btop,op,l,r,x,y,z;
    struct splay{int s[2],v,fa,siz,cnt;}t[N];
    int New(int x)
    {
        int u(btop?bin[btop--]:++idx);
        t[u].v=x,t[u].cnt=t[u].siz=1,
        t[u].fa=t[u].s[0]=t[u].s[1]=0;
        return u;
    }
    void update(int u)
    {t[u].siz=t[t[u].s[0]].siz+t[t[u].s[1]].siz+t[u].cnt;}
    void rotate(int x)
    {
        int y(t[x].fa),z(t[y].fa),k(t[t[x].fa].s[1]==x);
        if(z)t[z].s[t[t[y].fa].s[1]==y]=x;
        t[x].fa=z,t[y].s[k]=t[x].s[k^1],t[t[y].s[k]].fa=y;
        t[x].s[k^1]=y,t[y].fa=x;
        update(y),update(x);
    }
    void turn(int x)
    {
        for(int y(t[x].fa),z(t[y].fa);t[x].fa;y=t[x].fa,z=t[y].fa)
        {
            if(z)(t[y].s[0]==x)^(t[z].s[0]==y)?rotate(x):rotate(y);
            rotate(x);
        }
        update(x);
    }
    int getnum(int x,int k)
    {
        int u(root[k]),v(0);
        for(v=u;u;v=u)
        {
            if(t[u].v==x)return u;
            if(x<t[u].v)u=t[u].s[0];
            else u=t[u].s[1];
        }
        return v;
    }
    int Kth(int x,int k)
    {
        int u(root[k]);
        for(;u;)
        {
            if(x<=t[t[u].s[0]].siz)u=t[u].s[0];
            else if(x>t[t[u].s[0]].siz+t[u].cnt)
                x-=t[t[u].s[0]].siz+t[u].cnt,u=t[u].s[1];
            else return u;
        }
        return 0;
    }
    int getless(int x,int k)
    {
        int u(root[k]),cur(0);
        for(;u;)
            if(t[u].v<x)
                cur+=t[u].cnt+t[t[u].s[0]].siz,u=t[u].s[1];
            else u=t[u].s[0];
        return cur;
    }
    int getmax(int u){for(;t[u].s[1];u=t[u].s[1]);return u;}
    int getmin(int u){for(;t[u].s[0];u=t[u].s[0]);return u;}
    int getpre(int x,int k)
    {
        int u(getnum(x,k));
        if(!u)return -2147483647;
        turn(u),root[k]=u;
        if(t[u].v>=x)u=getmax(t[u].s[0]);
        return u?t[u].v:-2147483647;
    }
    int getnext(int x,int k)
    {
        int u(getnum(x,k));
        if(!u)return 2147483647;
        turn(u),root[k]=u;
        if(t[u].v<=x)u=getmin(t[u].s[1]);
        return u?t[u].v:2147483647;
    }
    void insert(int x,int k)
    {
        int u(getnum(x,k));
        if(t[u].v==x)
        {
            turn(u),root[k]=u;
            ++t[u].cnt,++t[u].siz;
            return;
        }
        u=New(x);
        if(!root[k]){root[k]=u;return;}
        int v(root[k]),w(0),dir(0);
        for(w=v;v;w=v)
            if(t[u].v<=t[v].v)dir=1,v=t[v].s[0];
            else dir=0,v=t[v].s[1];
        if(dir)t[w].s[0]=u;
        else t[w].s[1]=u;
        t[u].fa=w,turn(u),root[k]=u;
    }
    void Delete(int x,int k)
    {
        int u(getnum(x,k));
        turn(u);root[k]=u;
        if(t[u].cnt>1){--t[u].cnt,--t[u].siz;return;}
        if(t[u].siz==1)root[k]=0;
        else if(!t[u].s[0]||!t[u].s[1])
            root[k]=t[u].s[0]|t[u].s[1],t[root[k]].fa=0;
        else
        {
            t[t[u].s[0]].fa=0;
            int v(getmax(t[u].s[0]));
            turn(v);root[k]=v;
            t[v].s[1]=t[u].s[1],t[t[u].s[1]].fa=v,update(v);
        }
        bin[++btop]=u;
    }
    #undef ls
    #undef rs
    #define ls (p<<1)
    #define rs (p<<1|1)
    void build(int p,int l,int r)
    {
        for(int i(l);i<=r;++i)insert(a[i],p);
        if(l==r)return;
        int mid(l+r>>1);
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void segchange(int p,int l,int r,int v,int k)
    {
        Delete(a[k],p),insert(v,p);
        if(l==r)return;
        int mid(l+r>>1);
        if(k<=mid)segchange(ls,l,mid,v,k);
        else segchange(rs,mid+1,r,v,k);
    }
    int segless(int p,int l,int r,int kl,int kr,int v)
    {
        // cout<<"Wrong "<<l<<' '<<r<<' '<<kl<<' '<<kr<<'\n';
        if(l>=kl&&r<=kr)return getless(v,p);
        int mid(l+r>>1);
        int ll(0),rr(0);
        if(kl<=mid)ll=segless(ls,l,mid,kl,kr,v);
        else if(kr>mid)rr=segless(rs,mid+1,r,kl,kr,v);
        return ll+rr;

        // if(kl<=mid)return segless(ls,l,mid,kl,kr,v);
        // else if(kr>mid)return segless(rs,mid+1,r,kl,kr,v);
        // else return segless(ls,l,mid,kl,kr,v)+segless(rs,mid+1,r,kl,kr,v);
    }
    int segpre(int p,int l,int r,int kl,int kr,int v)
    {
        if(l>=kl&&r<=kr)return getpre(v,p);
        int mid(l+r>>1);
        if(kl<=mid)return segpre(ls,l,mid,kl,kr,v);
        else if(kr>mid)return segpre(rs,mid+1,r,kl,kr,v);
        else return max(segpre(ls,l,mid,kl,kr,v),segpre(rs,mid+1,r,kl,kr,v));
    }
    int segnext(int p,int l,int r,int kl,int kr,int v)
    {
        if(l>=kl&&r<=kr)return getnext(v,p);
        int mid(l+r>>1);
        if(kl<=mid)return segnext(ls,l,mid,kl,kr,v);
        else if(kr>mid)return segnext(rs,mid+1,r,kl,kr,v);
        else return min(segnext(ls,l,mid,kl,kr,v),segnext(rs,mid+1,r,kl,kr,v));
    }
    int segKth(int kl,int kr,int k)
    {
        int L(0),R(1e8+10);
        for(;L<R;)
        {
            int mid((L+R+1)>>1);
            if(segless(1,1,n,kl,kr,mid)>k-1)R=mid-1;
            else L=mid;
        }
        return L;
    }
    #undef ls
    #undef rs
}
namespace AC_Auto
{
    #define M 27
    string d,dd;
    int cnt;
    struct aa{bool ed;int son[M],nxt;}t[N];
    queue<int>q;
    void insert(string d)
    {
        int u(0),len(d.size());
        for(int i(0);i<len;++i)
        {
            int v(d[i]-'A');
            if(!t[u].son[v])t[u].son[v]=++cnt;
            u=t[u].son[v];
        }
        t[u].ed=1;
        return;
    }
    void nxt_set()
    {
        for(int i(0);i<26;++i)if(t[0].son[i])q.push(t[0].son[i]);
        for(;q.size();)
        {
            int u(q.front());q.pop();
            int Nxt(t[u].nxt);
            for(int i(0);i<26;++i)
            {
                int v(t[u].son[i]);
                if(!v){t[u].son[i]=t[Nxt].son[i];continue;}
                t[v].nxt=t[Nxt].son[i];
                t[v].ed|=t[t[v].nxt].ed;
                //假如失配指针是个终止节点,
                //由于失配指针的前缀和当前字符串后缀相同，
                //所以实际上另一个字符串已经结束了。
                q.push(v);
            }
        }
    }
    #undef M
}
#undef N
#define N (200010)
namespace Bipartite_Graph
{
    bitset<N>flag;
    int matx[N],maty[N];
    int dis[N],v[N],head[N],cnt;
    struct aa{int nxt,to,w;}e[N<<1];
    void add(int u,int v,int w)
    {e[++cnt]={head[u],v,w};head[u]=cnt;}
    bool hungarian(int x)
    {
        for(int i(head[x]),y;i;i=e[i].nxt)
        {
            if(!flag[y=e[i].to])
            {
                flag[y]=true;
                if(!maty[y]||hungarian(maty[y]))
                {
                    matx[x]=y,maty[y]=x;
                    return true;
                }
            }
        }
        return false;
    }
    int Hungary()
    {
        int tot(0);
        for(int i(1);i<=n;++i)
        {
            for(int j(1);j<=n;++j)flag[j]=false;
            if(hungarian(i))++tot;
        }
        return tot;
    }
    bool dfs(int x,int color)
    {
        v[x]=color;
        for(int i(head[x]);i;i=e[i].nxt)
            if(!v[e[i].to]&&!dfs(e[i].to,3-color))return false;
            else if(v[e[i].to]==color) return false;
        return true;
    }
    bool cal(int m)
    {
        for(int i(1);i<=n;++i)if(!v[i])if(!dfs(i,1))return false;
        return true;
    }
    //二分图的判定
}
namespace Network_flow
{
    bitset<N>flag;
    int s,t,maxf;
    int incf[N],pre[N];
    int dis[N],head[N],cnt(1);
    struct aa{int nxt,to,w;}e[N<<1];
    void add(int u,int v,int w)
    {e[++cnt]={head[u],v,w};head[u]=cnt;}
    namespace Edmond_karp
    {
        bool bfs()
        {
            for(int i(0);i<=(n*m+1)<<1;++i)flag[i]=false;
            queue<int>q;
            incf[s]=1<<30;
            q.push(s),flag[s]=true;
            for(;q.size();)
            {
                int x(q.front());q.pop();
                for(int i(head[x]);i;i=e[i].nxt)
                    if(e[i].w)
                    {
                        int y(e[i].to);
                        if(flag[y])continue;
                        incf[y]=min(incf[x],e[i].w);
                        pre[y]=i;
                        q.push(y),flag[y]=true;
                        if(y==t)return true;
                    }
            }
            return false;
        }
        void update()
        {
            int x(t);
            for(int i(pre[x]);x^s;x=e[i^1].to,i=pre[x])
                e[i].w-=incf[t],e[i^1].w+=incf[t];
            maxf+=incf[t];
        }
    }
    namespace Dinic
    {
        int now[N],d[N];
        bool bfs()
        {
            for(int i(0);i<=(n*m+1)<<1;++i)d[i]=0;
            queue<int>q;
            q.push(s),d[s]=1,now[s]=head[s];
            for(;q.size();)
            {
                int x(q.front());q.pop();
                for(int i(head[x]);i;i=e[i].nxt)
                    if(e[i].w&&!d[e[i].to])
                    {
                        int y(e[i].to);
                        q.push(y);
                        now[y]=head[y];
                        d[y]=d[x]+1;
                        if(y==t)return true;
                    }
            }
            return false;
        }
        int dinic(int x,int flow)
        {
            if(x==t)return flow;
            int rest(flow),k;
            for(int i(now[x]);i&&rest;i=e[i].nxt)
            {
                now[x]=i;
                if(e[i].w&&d[e[i].to]==d[x]+1)
                {
                    int y(e[i].to);
                    k=dinic(y,min(rest,e[i].w));
                    if(!k)d[y]=0;
                    e[i].w-=k;
                    e[i^1].w+=k;
                    rest-=k;
                }
            }
            return flow-rest;
        }
    }
}
namespace zkw_Segment_tree
{
    int len(1),inf((1ll<<31)-1);
    struct segment_tree
    {
        int sum,min,max,add;
    }t[N<<1];
    inline void build()
    {
        for(;len<=n+1;len<<=1);// 或许需要大于n+1
        for(int i(len+1);i<=len+n;++i)
            t[i].sum=t[i].min=t[i].max=read();
        for(int i(len-1);i;--i)
            t[i].sum=t[i<<1].sum+t[i<<1|1].sum,
            t[i].min=min(t[i<<1].min,t[i<<1|1].min),
            t[i<<1].min-=t[i].min,
            t[i<<1|1].min-=t[i].min,
            t[i].max=max(t[i<<1].max,t[i<<1|1].max),
            t[i<<1].max-=t[i].max,
            t[i<<1|1].max-=t[i].max;
    }
    inline void update(int p,int v)
    {
        int x;
        for(p+=len;p;p>>=1)
            t[p].sum+=v,t[p].min+=v,t[p].max+=v,
            x=min(t[p].min,t[p^1].min),t[p].min-=x,
            t[p^1].min-=x,t[p>>1].min+=x,
            x=max(t[p].max,t[p^1].max),t[p].max-=x,
            t[p^1].max-=x,t[p>>1].max+=x;
    }
    inline void update(int l,int r,int v)
    {
        if(l==r){update(l,v);return;}
        int lc(0),rc(0),pos(1),tmp;
        for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1,pos<<=1)
        {
            t[l].sum+=lc*v,t[r].sum+=rc*v;
            if(~l&1)t[l^1].sum+=pos*v,t[l^1].add+=v,lc+=pos;
            if(r&1)t[r^1].sum+=pos*v,t[r^1].add+=v,rc+=pos;
            tmp=min(t[l].min,t[l^1].min),t[l].min-=tmp,
            t[l^1].min-=tmp,t[l>>1].min+=tmp,
            tmp=min(t[r].min,t[r^1].min),t[r].min-=tmp,
            t[r^1].min-=tmp,t[r>>1].min+=tmp,
            tmp=max(t[l].max,t[l^1].max),t[l].max-=tmp,
            t[l^1].max-=tmp,t[l>>1].max+=tmp,
            tmp=max(t[r].max,t[r^1].max),t[r].max-=tmp,
            t[r^1].max-=tmp,t[r>>1].max+=tmp;
        }
        for(;l;l>>=1,r>>=1)
            t[l].sum+=lc*v,t[r].sum+=rc*v,
            tmp=min(t[l].min,t[l^1].min),t[l].min-=tmp,
            t[l^1].min-=tmp,t[l>>1].min+=tmp,
            tmp=max(t[l].max,t[l^1].max),t[l].max-=tmp,
            t[l^1].max-=tmp,t[l>>1].max+=tmp;
    }
    inline int querysum(int l,int r)
    {
        int ans(0),lc(0),rc(0),pos(1);
        for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1,pos<<=1)
        {
            ans+=t[l].add*lc+t[r].add*rc;
            if(~l&1)ans+=t[l^1].sum,lc+=pos;
            if(r&1)ans+=t[r^1].sum,rc+=pos;
        }
        for(;l;l>>=1,r>>=1)ans+=t[l].add*lc+t[r].add*rc;
        return ans;
    }
    inline int querymin(int l,int r)
    {
        int lans(0),rans(0),ans(0);
        if(l==r)
        {
            for(l+=len;l;l>>=1)
                lans+=t[l].min;
            return lans;
        }
        for(l+=len,r+=len;l^r^1;l>>=1,r>>=1)
        {
            lans+=t[l].min,rans+=t[r].min;
            if(~l&1)lans=min(lans,t[l^1].min);
            if(r&1)rans=min(rans,t[r^1].min);
        }
        for(ans=min(lans+t[l].min,rans+t[r].min);l>1;ans+=t[l>>=1].min);
        return ans;
    }
    inline int querymax(int l,int r)
    {
        int lans(0),rans(0),ans(0);
        if(l==r)
        {
            for(l+=len;l;l>>=1)
                lans+=t[l].max;
            return lans;
        }
        for(l+=len,r+=len;l^r^1;l>>=1,r>>=1)
        {
            lans+=t[l].max,rans+=t[r].max;
            if(~l&1)lans=max(lans,t[l^1].max);
            if(r&1)rans=max(rans,t[r^1].max);
        }
        for(ans=max(lans+t[l].max,rans+t[r].max);l>1;ans+=t[l>>=1].max);
        return ans;
    }
}
namespace martix
{
    struct aa
    {
        int g[N][N],x,y;
        void clear(){memset(g,0,sizeof(g));}
    }furina,fucaros,fontaine,sumeru;
    aa cal(aa a,aa b,int t,int q,int l,int P=P)
    {
        aa c;
        c.x=t,c.y=l;
        c.clear();
        for(int i(1);i<=t;++i)
            for(int j(1);j<=q;++j)
                for(int k(1);k<=l;++k)
                    (c.g[i][k]+=a.g[i][j]*b.g[j][k])%=P;
        return c;
    }
    aa operator *(const aa&a,const aa&b)
    {return cal(a,b,a.x,a.y,b.y,P);}
    aa qpow(int b,int P=P)
    {
        furina=fucaros;
        sumeru=fucaros;
        for(;b;b>>=1)
        {
            if(b&1)
                furina=furina*sumeru;
            sumeru=sumeru*sumeru;
        }
        return furina;
    }
}
namespace Complex
{
    class C
    {
        public:
        double r,i;
        C(){}
        C(double a,double b){r=a,i=b;}

        C operator+(C x){return C(r+x.r,i+x.i);}
        C operator-(C x){return C(r-x.r,i-x.i);}
        C operator*(C x){return C(r*x.r-i*x.i,r*x.i+i*x.r);}
        C operator/(C x)
        {
            int r((r*x.r+i*x.i)/(x.r*x.r+x.i*x.i));
            int i((i*x.r+r*x.i)/(x.r*x.r+x.i*x.i));
            return C(r,i);
        }
        C operator-(){return C(-r,-i);}

        C operator+=(C x){*this=*this+x;return *this;}
        C operator-=(C x){*this=*this-x;return *this;}
        C operator*=(C x){*this=*this*x;return *this;}
        C operator/=(C x){*this=*this/x;return *this;}

        C operator+(double x){return C(r+x,i);}
        C operator-(double x){return C(r-x,i);}
        C operator*(double x){return C(r*x,i*x);}
        C operator/(double x){return C(r/x,i/x);}
        C operator+=(double x){*this=*this+x;return *this;}
        C operator-=(double x){*this=*this-x;return *this;}
        C operator*=(double x){*this=*this*x;return *this;}
        C operator/=(double x){*this=*this/x;return *this;}

        C operator+(int x){return C(r+x,i);}
        C operator-(int x){return C(r-x,i);}
        C operator*(int x){return C(r*x,i*x);}
        C operator/(int x){return C(r/x,i/x);}
        C operator+=(int x){*this=*this+x;return *this;}
        C operator-=(int x){*this=*this-x;return *this;}
        C operator*=(int x){*this=*this*x;return *this;}
        C operator/=(int x){*this=*this/x;return *this;}
        
    }furina[N],fucaros[N],fontaine[N],rt[N],rq[N];
    int A,B,L,R[N];
    void FFT(C a[],int n)
    {
        for(int i(0);i<n;++i)
            if(R[i]>i)
                swap(a[R[i]],a[i]);
        for(int t(n>>1),d(1);d<n;d<<=1,t>>=1)
            for(int i(0);i<n;i+=(d<<1))
                for(int j(0);j<d;++j)
                {
                    C tmp(fontaine[t*j]*a[i+j+d]);
                    a[i+j+d]=a[i+j]-tmp;
                    a[i+j]+=tmp;
                }
    }
}
namespace Segment_Tree
{
    #define ls (p<<1)
    #define rs (p<<1|1)
    struct tt
    {
        int l,r,sum,add,min,max;
    }t[N<<2];
    inline void push_up(int p)
    {
        t[p].sum=t[ls].sum+t[rs].sum;
        t[p].min=min(t[ls].min,t[rs].min);
        t[p].max=max(t[ls].max,t[rs].max);
    }
    inline void push_down(int p)
    {
        if(t[p].add)
            t[ls].add+=t[p].add,
            t[rs].add+=t[p].add,
            t[ls].min+=t[p].add,
            t[rs].min+=t[p].add,
            t[ls].max+=t[p].add,
            t[rs].max+=t[p].add,
            t[ls].sum+=t[p].add*(t[ls].r-t[ls].l+1),
            t[rs].sum+=t[p].add*(t[rs].r-t[rs].l+1),
            t[p].add=0;
    }
    void build(int p,int l,int r)
    {
        t[p].l=l,t[p].r=r;
        if(l==r){t[p].sum=t[p].min=t[p].max=a[l];return;}
        int mid(l+r>>1);
        build(ls,l,mid),build(rs,mid+1,r);
        push_up(p);
    }
    void update(int p,int l,int r,int v)
    {
        if(t[p].l>=l&&t[p].r<=r)
        {
            t[p].sum+=v*(t[p].r-t[p].l+1),
            t[p].min+=v,t[p].max+=v,
            t[p].add+=v;
            return;
        }
        int mid(t[p].l+t[p].r>>1);
        push_down(p);
        if(l<=mid)update(ls,l,r,v);
        if(r>mid)update(rs,l,r,v);
        push_up(p);
    }
    int query(int p,int l,int r)
    {
        if(t[p].l>=l&&t[p].r<=r)
            return t[p].sum;
        int mid(t[p].l+t[p].r>>1),sum(0);
        push_down(p);
        if(l<=mid)sum+=query(ls,l,r);
        if(r>mid)sum+=query(rs,l,r);
        push_up(p);
        return sum;
    }
    int querymin(int p,int l,int r)
    {
        if(t[p].l>=l&&t[p].r<=r)
            return t[p].min;
        int mid(t[p].l+t[p].r>>1),minn(0x7f7f7f7f);
        push_down(p);
        if(l<=mid)minn=min(minn,querymin(ls,l,r));
        if(r>mid)minn=min(minn,querymin(rs,l,r));
        push_up(p);
        return minn;
    }
    int querymax(int p,int l,int r)
    {
        if(t[p].l>=l&&t[p].r<=r)
            return t[p].max;
        int mid(t[p].l+t[p].r>>1),maxx(-0x7f7f7f7f);
        push_down(p);
        if(l<=mid)maxx=max(maxx,querymax(ls,l,r));
        if(r>mid)maxx=max(maxx,querymax(rs,l,r));
        push_up(p);
        return maxx;
    }
    #undef ls
    #undef rs
}
*/