ll query(int x){ll re=0;for(int i=x;i;i-=i&-i)re+=t[i];return re;}
void modify(int x,int val){if(x>m)return;for(int i=x;i<=m;i+=i&-i)t[i]+=val;}

#define lson (x<<1)
#define rson (x<<1|1)
const int maxn=1e5+6;
int a[maxn],n,m;ll sum[maxn<<2],add[maxn<<2];
void pushup(int x){sum[x]=sum[lson]+sum[rson];}
void pushdown(int x,int l,int r){
	if(!add[x])return;
	ll tag=add[x];add[x]=0;int mid=(l+r)>>1;
	add[lson]+=tag;add[rson]+=tag;
	sum[lson]+=tag*1ll*(mid-l+1);sum[rson]+=tag*1ll*(r-mid);
}
void build(int x,int l,int r){
	if(l==r){sum[x]=a[l];return;}
	int mid=(l+r)>>1;
	build(lson,l,mid);build(rson,mid+1,r);
	pushup(x);
}
void modify(int x,int l,int r,int ql,int qr,ll v){
	if(ql<=l&&r<=qr){sum[x]+=v*1ll*(r-l+1),add[x]+=v;return;}
	int mid=(l+r)>>1;pushdown(x,l,r);
	if(ql<=mid)modify(lson,l,mid,ql,qr,v);
	if(qr>mid)modify(rson,mid+1,r,ql,qr,v);
	pushup(x);
}
inline ll querysum(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return sum[x];
	pushdown(x,l,r);
	int mid=(l+r)>>1;ll re=0;
	if(ql<=mid)re+=querysum(lson,l,mid,ql,qr);
	if(qr>mid)re+=querysum(rson,mid+1,r,ql,qr);
	return re;
}
int main()
{
	n=read(),m=read();
	rep(i,1,n)a[i]=read();
	build(1,1,n);
	rep(i,1,m){
		int opt=read(),l=read(),r=read();
		if(opt==1){ll k=read();modify(1,1,n,l,r,k);}
		else printf("%lld\n",querysum(1,1,n,l,r));
	}
	return 0;
}

#include<iostream>
#include<cstdio>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e6+6;
struct tree{int l,r,w,d;}t[maxn];
int n,m,fa[maxn];
bool die[maxn];
char ch[10];
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}

int merge(int x,int y)
{
    if(x==0||y==0)return x+y;
    if(t[x].w>t[y].w||(t[x].w==t[y].w&&x>y))swap(x,y);
    t[x].r=merge(t[x].r,y);
    if(t[t[x].l].d<t[t[x].r].d)swap(t[x].l,t[x].r);
    t[x].d=t[t[x].r].d+1;
    return x;
}

int main()
{
    n=read();m=read();
    rep(i,1,n)t[i].w=read();
    t[0].d=-1;rep(i,1,n)fa[i]=i;
    rep(i,1,m){
        int opt=read();
        if(opt==1){
            int x=read(),y=read();
            if(die[x]||die[y])continue;
            int r1=find(x),r2=find(y);
            if(r1!=r2){int t=merge(r1,r2);fa[r1]=fa[r2]=t;}
        }
        if(opt==2){
            int x=read();
            if(die[x])printf("-1\n");
            else{
                int r1=find(x);die[r1]=1;
                printf("%d\n",t[r1].w);
                fa[r1]=merge(t[r1].l,t[r1].r);fa[fa[r1]]=fa[r1];
            }
        }
    }
    return 0;
}       

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e5+6;
struct tree{int l,r,size,w,f;}t[maxn<<1];
int n,len=0,root=0;
inline int getrank(){return (rand()<<16)+rand();}
void change(int x){
    if(x==0)return;
    t[x].size=t[t[x].l].size+t[t[x].r].size+1;
}
int merge(int x,int y){
    if(x==0||y==0)return x+y;
    if(t[x].f>t[y].f){
        t[x].r=merge(t[x].r,y);change(x);return x;}
    else{t[y].l=merge(x,t[y].l);change(y);return y;}
}
void splite(int x,int val,int &new1,int &new2){
    if(x==0){new1=0;new2=0;return;}
    if(t[x].w<val){
        new1=x;splite(t[x].r,val,t[x].r,new2);
    }else{new2=x;splite(t[x].l,val,new1,t[x].l);}
    change(x);
}
int insert(int now,int want){
    if(now==0)return want;
    if(t[now].f>t[want].f){
        if(t[now].w<t[want].w)t[now].r=insert(t[now].r,want);else t[now].l=insert(t[now].l,want);
        change(now);return now;
    }
    splite(now,t[want].w,t[want].l,t[want].r);change(want);return want;
}

int find(int now,int want){
    if(t[t[now].l].size==want-1)return t[now].w;
    if(t[t[now].l].size>=want)return find(t[now].l,want);
    return find(t[now].r,want-t[t[now].l].size-1);
}
int findleft(int now){while(t[now].l)now=t[now].l;return t[now].w;}
int findright(int now){while(t[now].r)now=t[now].r;return t[now].w;}

int main()
{
    srand(1125);
    n=read();
    mem(t,0);
    rep(i,1,n){
        int opt=read();
        if (opt==1){int x=read();t[++len].f=getrank();t[len].w=x;t[len].size=1;root=insert(root,len);}
        else if(opt==2){int x=read(),new1,new2,new3;splite(root,x,new1,new2);splite(new2,x+1,new2,new3);root=merge(merge(new1,t[new2].l),merge(t[new2].r,new3));}
        else if(opt==3){int x=read(),new1,new2;splite(root,x,new1,new2);printf("%d\n",t[new1].size+1);root=merge(new1,new2);}
        else if(opt==4){int x=read();printf("%d\n",find(root,x));}
        else if(opt==5){int x=read(),new1,new2;splite(root,x,new1,new2);printf("%d\n",findright(new1));root=merge(new1,new2);}
        else{int x=read(),new1,new2;splite(root,x+1,new1,new2);printf("%d\n",findleft(new2));root=merge(new1,new2);}
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e5+6;
int n,m,sz,rt,fa[maxn],c[maxn][2],id[maxn],size[maxn];
bool rev[maxn];
void pushup(int k)
{
    int l=c[k][0],r=c[k][1];
    size[k]=size[l]+size[r]+1;
}
void pushdown(int k)
{
    int l=c[k][0],r=c[k][1];
    if(rev[k]){
        swap(c[k][0],c[k][1]);
        rev[l]^=1;rev[r]^=1;
        rev[k]=0;
    }
}
void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l,r;
    if(c[y][0]==x)l=0;else l=1;
    r=l^1;
    if(y==k)k=x;
    else{
        if(c[z][0]==y)c[z][0]=x;
        else c[z][1]=x;
    }
    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
    c[y][l]=c[x][r];c[x][r]=y;
    pushup(y);pushup(x);
}
void splay(int x,int &k)
{
    while(x!=k){
        int y=fa[x],z=fa[y];
        if(y!=k){
            if(c[y][0]==x^c[z][0]==y)rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}
int find(int k,int rank)
{
    pushdown(k);
    int l=c[k][0],r=c[k][1];
    if(size[l]+1==rank)return k;
    else if(size[l]>=rank)return find(l,rank);
    else return find(r,rank-size[l]-1);
}
void rever(int l,int r){
    int x=find(rt,l),y=find(rt,r+2);
    splay(x,rt);splay(y,c[x][1]);
    int z=c[y][0];
    rev[z]^=1;
}
void build(int l,int r,int f)
{
    if(l>r)return;
    int now=id[l],last=id[f];
    if(l==r){
        fa[now]=last;size[now]=1;
        if(l<f)c[last][0]=now;
        else c[last][1]=now;
        return;
    }
    int mid=(l+r)>>1;now=id[mid];
    build(l,mid-1,mid);build(mid+1,r,mid);
    fa[now]=last;pushup(mid);
    if(mid<f)c[last][0]=now;
    else c[last][1]=now;
}

int main()
{
    n=read(),m=read();
    rep(i,1,n+2)id[i]=++sz;
    build(1,n+2,0);rt=(n+3)>>1;
    rep(i,1,m){
        int l=read(),r=read();
        rever(l,r);
    }
    rep(i,2,n+1)printf("%d ",find(rt,i)-1);
    return 0;
}

#define lson (x<<1)
#define rson (x<<1|1) 
const int maxn=3e5+6;
struct tree{int l,r,v,lazy;}node[maxn<<1];
struct edge{int to,next;}e[maxn<<2];
int last[maxn],w[maxn],ex[maxn],top[maxn],rank[maxn],size[maxn],dep[maxn],tt[maxn],fa[maxn],cnt;
int mod,n,m,s,tid[maxn],tot;
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;tt[u]++;}
void pushdown(int x){
	if(node[x].lazy==0)return;
	node[x].v+=node[x].lazy*(node[x].r-node[x].l+1)%mod;
	node[lson].lazy+=node[x].lazy;node[rson].lazy+=node[x].lazy;
	node[x].lazy=0;
}
void build(int x,int l,int r){
	int mid=(l+r)>>1;node[x].l=l,node[x].r=r;
	if(l==r)return;
	build(lson,l,mid);
	build(rson,mid+1,r);
}
void modify(int x,int l,int r,int val){
	if(node[x].l>r||node[x].r<l)return;
	if(node[x].l>=l&&node[x].r<=r){node[x].lazy+=val;pushdown(x);return;}
	modify(lson,l,r,val);
	modify(rson,l,r,val);
	pushdown(lson);pushdown(rson);
	node[x].v=(node[lson].v+node[rson].v)%mod;
}
inline int query(int x,int l,int r){
	if(node[x].l>r||node[x].r<l)return 0;
	if(node[x].l>=l&&node[x].r<=r)return (node[x].v)%mod;
	pushdown(lson);pushdown(rson);
	return (query(lson,l,r)+query(rson,l,r))%mod;
}
void dfs(int x,int Fa){
	size[x]=1;dep[x]=dep[Fa]+1;fa[x]=Fa;
	reg(x){
		if(e[i].to==Fa)continue;
		dfs(e[i].to,x);
		size[x]+=size[e[i].to];
	}
}
void dfs2(int x,int head){
    int mson=0; 
    top[x]=head;tid[x]=++tot;rank[tid[x]]=tot; 
	modify(1,tot,tot,w[x]); 
    if(tt[x]==1&&x!=s){ex[x]=x;return;}
    reg(x)
    	if(size[e[i].to]<size[x]&&size[e[i].to]>size[mson])mson=e[i].to; 
    dfs2(mson,head); 
    ex[x]=ex[mson]; 
    reg(x)
    	if(size[e[i].to]<size[x]&&e[i].to!=mson){dfs2(e[i].to,e[i].to);ex[x]=ex[e[i].to];}
}
void pmodify(int x,int y,int val){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		modify(1,tid[top[x]],tid[x],val);
		x=fa[top[x]];
	}
	if(tid[x]>tid[y])swap(x,y);
	modify(1,tid[x],tid[y],val);
}
inline int pquery(int x,int y){
	int re=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		re=(re+query(1,tid[top[x]],tid[x]))%mod;
		x=fa[top[x]];
	}
	if(tid[x]>tid[y])swap(x,y);
	re=(re+query(1,tid[x],tid[y]))%mod;
	return re;
}		
int main()
{
	n=read(),m=read(),s=read(),mod=read();
	rep(i,1,n)w[i]=read();
	rep(i,1,n-1){
		int u=read(),v=read();
		insert(u,v);insert(v,u);
	}
	build(1,1,n);
	dfs(s,0);dfs2(s,s);
	rep(i,1,m){
		int opt=read();
		if(opt==1){int x=read(),y=read(),z=read();pmodify(x,y,z);}
		if(opt==2){int x=read(),y=read();printf("%d\n",pquery(x,y)%mod);}
		if(opt==3){int x=read(),y=read();modify(1,tid[x],tid[ex[x]],y);}
		if(opt==4){int x=read();printf("%d\n",query(1,tid[x],tid[ex[x]])%mod);}
	}
	return 0;
}

const int maxn=3e5+6;
int n,m,top,c[maxn][2],fa[maxn],v[maxn],s[maxn],que[maxn];
bool rev[maxn];
void update(int x){
	int l=c[x][0],r=c[x][1];
	s[x]=s[l]^s[r]^v[x];
}
void pushdown(int x){
	int l=c[x][0],r=c[x][1];
	if(rev[x]){
		rev[x]^=1;rev[l]^=1;rev[r]^=1;
		swap(c[x][0],c[x][1]);
	}
}
bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void rotate(int x){
	int y=fa[x],z=fa[y],l,r;
	if(c[y][0]==x)l=0;else l=1;r=l^1;
	if(!isroot(y)){
		if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;
	}
	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x){
	top=0;que[++top]=x;
	for(int i=x;!isroot(i);i=fa[i])que[++top]=fa[i];
	dep(i,top,1)pushdown(que[i]);
	while(!isroot(x)){
		int y=fa[x],z=fa[y];
		if(!isroot(y)){
			if(c[y][0]==x^c[z][0]==y)rotate(x);else rotate(y);
		}
		rotate(x);
	}
}
void access(int x){
	for(int t=0;x;t=x,x=fa[x])splay(x),c[x][1]=t,update(x);
}
void makeroot(int x){
	access(x);splay(x);rev[x]^=1;
}
int find(int x){
	access(x);splay(x);
	while(c[x][0])x=c[x][0];
	return x;
}
void cut(int x,int y){
	makeroot(x);access(y);splay(y);
	if(c[y][0]==x)c[y][0]=fa[x]=0;
}
void link(int x,int y){
	makeroot(x);fa[x]=y;
}
int main()
{
	n=read(),m=read();
	rep(i,1,n)v[i]=read(),s[i]=v[i];
	rep(i,1,m){
		int opt=read(),x=read(),y=read();
		if(opt==0){makeroot(x);access(y);splay(y);printf("%d\n",s[y]);}
		if(opt==1){if(find(x)!=find(y))link(x,y);}
		if(opt==2){if(find(x)==find(y))cut(x,y);}
		if(opt==3){access(x);splay(x);v[x]=y;update(x);}
	}
	return 0;
}

const int maxn=1e5+6,maxm=2e6+6;
int n,m,tot,sz,cnt,ind,now,num[maxn],pos[maxn],v[maxn],tmp[maxn],hash[maxn],root[maxn];
int last[maxn],deep[maxn],fa[maxn][17],ls[maxm],rs[maxm],sum[maxm];
struct edge{int to,next;}e[maxm];

void insert(int u,int v){
    e[++cnt]=(edge){v,last[u]};last[u]=cnt;
    e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}

inline int find(int x){
    int l=1,r=tot,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(hash[mid]<x)l=mid+1;else r=mid-1;
    }
    return l;
}
void dfs(int x){
    num[++ind]=x;pos[x]=ind;
    rep(i,1,16)if((1<<i)<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];else break;
    reg(x)
        if(fa[x][0]!=e[i].to){
            deep[e[i].to]=deep[x]+1;
            fa[e[i].to][0]=x;
            dfs(e[i].to);
        }
}
int lca(int x,int y){
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    rep(i,0,16)if((1<<i)&t)x=fa[x][i];
    dep(i,16,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    if(x==y)return x;else return fa[x][0];
}
void update(int l,int r,int x,int &y,int v){
    y=++sz;sum[y]=sum[x]+1;
    if(l==r)return;
    ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;
    if(v<=mid)update(l,mid,ls[x],ls[y],v);else update(mid+1,r,rs[x],rs[y],v);
}
int query(int x,int y,int rank){
    int a=x,b=y,c=lca(x,y),d=fa[c][0];
    a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
    int l=1,r=tot,mid;
    while(l<r){
        mid=(l+r)>>1;
        int t=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
        if(t>=rank)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];
        else rank-=t,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
    }
    return hash[l];
}

    void work()  
    {  
        fac[0]=fac[1]=inv[0]=inv[1]=1;  
        rep(i,2,p-1)fac[i]=fac[i-1]*i%p;  //阶乘预处理
        rep(i,2,p-1)inv[i]=(p-p/i)*inv[p%i]%p;  
        rep(i,1,p-1)inv[i]=inv[i-1]*inv[i]%p;  //逆元预处理
    }  
    ll C(ll n,ll m)  
    {  
        if(n<m)return 0;  //舍去组合数无意义的情况
        if(n<p&&m<p)return fac[n]*inv[m]%p*inv[n-m]%p;  
        return C(n/p,m/p)*C(n%p,m%p)%p;  
    }  

void exgcd(int a,int b,LL &x,LL &y){  
    if(b==0){x=1,y=0;return;}  
    exgcd(b,a%b,x,y);  
    LL t=x;  
    x=y,y=t-a/b*y;  
}  

void shaker()  {  
    int j;phi[1]=1;  
    rep(i,2,n){  
        if(!not_prime[i]){prime[++top]=i;phi[i]=i-1;}  
        for(j=1;j<=top&&i*prime[j]<=n;j++){  
            not_prime[prime[j]*i]=1;  
            if(i%prime[j]==0){phi[prime[j]*i]=phi[i]*prime[j];break;}  
            phi[prime[j]*i]=phi[i]*(prime[j]-1);  
        }  
    }  
} 

    mu[1]=1;
    rep(i,2,maxn-6){
        if(!is_prime[i])prime[++cnt]=i,mu[i]=-1;
        rep(j,1,cnt){
            if(prime[j]*i>maxn-6)break;
            is_prime[i*prime[j]]=1;
            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }

const int maxn=2e5+6;
typedef complex<double> E;
int n,m,L;
char ch[maxn];
int R[maxn],c[maxn];
E a[maxn],b[maxn];

void fft(E *a,int f)
{
    rep(i,0,n-1)
        if(i<R[i])swap(a[i],a[R[i]]);
    for(int i=1;i<n;i<<=1){
        E wn(cos(pi/i),f*sin(pi/i));
        for(int j=0;j<n;j+=(i<<1)){
            E w(1,0);
            for(int k=0;k<i;k++,w*=wn){
                E x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y;
                a[j+k+i]=x-y;
            }
        }
    }
    if(f==-1)rep(i,0,n-1)a[i]/=n;
}

int main()
{
    n=read();n--;
    scanf("%s",ch);
    rep(i,0,n)a[i]=ch[n-i]-'0';
    scanf("%s",ch);
    rep(i,0,n)b[i]=ch[n-i]-'0';
    m=2*n;
    for(n=1;n<=m;n<<=1)L++;
    rep(i,0,n-1)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
    fft(a,1);fft(b,1);
    rep(i,0,n)a[i]*=b[i];
    fft(a,-1);
    rep(i,0,m)c[i]=(int)(a[i].real()+0.1);
    rep(i,0,m)
        if(c[i]>=10){
            c[i+1]+=c[i]/10,c[i]%=10;
            if(i==m)m++;
        }
    dep(i,m,0)printf("%d",c[i]);
    return 0;
}

#define inf 1e9
const int maxn=500;
int Map[maxn][maxn],n,m,S;
void Pre(){
	rep(i,1,n)
		rep(j,1,n)Map[i][j]=(i==j?0:inf);
}
void Floyd(){
    rep(k,1,n)
		rep(i,1,n)
			rep(j,1,n)
				Map[i][j]=min(Map[i][k]+Map[k][j],Map[i][j]);
}

#define inf 0x7fffffff
const int maxn=1e4+6,maxm=5e5+6;
struct edge{int to,next,w;}e[maxm<<1];
int n,m,S,dis[maxn],que[maxn<<2],last[maxn],cnt=0;
bool inq[maxn];
void Pre(){rep(i,1,n)dis[i]=inf;dis[S]=0;}
void insert(int u,int v,int w){
	e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
}
void SPFA(){
	int head=0,tail=1;
	que[head]=S;dis[S]=0;inq[S]=1;
	while(head<tail){
		int now=que[head++];
		reg(now)
			if(dis[e[i].to]>dis[now]+e[i].w){
				dis[e[i].to]=dis[now]+e[i].w;
				if(!inq[e[i].to])inq[e[i].to]=1,que[tail++]=e[i].to;
			}
		inq[now]=0;
	}
}

const int maxn=5e3+6,maxm=2e5+6;
int n,m,fa[maxn],cnt;ll ans=0;
struct Kedge{int u,v,w;}Ke[maxm<<1];
void Pre(){rep(i,1,n)fa[i]=i;}
inline int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
inline bool Kcmp(Kedge a,Kedge b){return a.w<b.w;}
void Kruscal(){
	sort(Ke+1,Ke+1+m,Kcmp);
	rep(i,1,m){
		int root1=findfa(Ke[i].u),root2=findfa(Ke[i].v);
		if(root1!=root2)fa[root1]=root2,cnt++,ans+=Ke[i].w;
		if(cnt==n-1)break;
	}
}

const int maxn=2006;  
int n,cnt=0,scc,top=0,tim,lim,ans=0;  
int head[maxn],h[maxn],r[maxn],dfn[maxn],low[maxn],que[maxn],inque[maxn];  
int belong[maxn],hav[maxn],mark[maxn][maxn];  
char ch[maxn];  
struct edge{int to,next;}e[4000006],ed[4000006];  
#define reg(x) for(int i=head[x];i;i=e[i].next)  
#define v e[i].to  
#define newreg(x) for(int i=h[x];i;i=ed[i].next)  
#define newv ed[i].to  
void tarjan(int x)  
{  
    int now=0;  
    dfn[x]=low[x]=++tim;que[++top]=x;inque[x]=1;  
    reg(x)  
        if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}  
        else if(inque[v])low[x]=min(low[x],dfn[v]);  
    if(low[x]==dfn[x]){  
        scc++;  
        while(now!=x){  
            now=que[top--];  
            inque[now]=0;belong[now]=scc;hav[scc]++;  
        }  
    }  
}  
  
void rebuild()  
{  
    cnt=0;  
    rep(k,1,n)  
        reg(k)  
            if(belong[k]!=belong[v])ed[++cnt]=(edge){belong[k],h[belong[v]]},h[belong[v]]=cnt,r[belong[k]]++;  
}  

const int maxn=1506;  
int match[maxn][maxn],use[maxn],result[maxn],n,m,ans=0;  
bool dfs(int now)  
{  
    rep(i,0,n-1)  
        if(match[now][i]&&!use[i]){  
            use[i]=true;  
            if(!result[i]||dfs(result[i])){  
                result[i]=now;  
                return true;  
            }  
        }  
    return false;  
}  
int main()  
{  
    n=read(),m=read();  
    rep(i,1,m){  
        int x=read(),y=read();  
        match[i][x]=match[i][y]=1;  
    }  
    rep(i,1,m){  
        mem(use,0);  
        if(dfs(i))ans++;else break;  
    }  
    cout<<ans<<endl;  
    return 0;  
}  

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define ll long long
#define mem(x,num) memset(x,num,sizeof(x))
#define inf 1844387848
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e5+6,maxq=1e6+6;
struct edge{ll to,from,v,t,next;}e[maxn<<1];
ll n,m,k,cnt=1,ans,s,t,last[maxn],que[maxq],h[maxq];

bool bfs()
{
    ll head=0,tail=0,now;
    mem(h,-1);que[0]=s,h[s]=0;
    while(head<=tail){
        now=que[head++];
        reg(now)
            if(e[i].v&&h[e[i].to]==-1){h[e[i].to]=h[now]+1;que[++tail]=e[i].to;}
    }
    if(h[t]==-1)return 0;else return 1;
}
int dfs(int x,int f)
{
    if(x==t)return f;
    ll w,used=0;
    reg(x)
        if(e[i].v&&h[e[i].to]==h[x]+1){
            w=f-used;w=dfs(e[i].to,min(w,e[i].v));
            e[i].v-=w;e[i^1].v+=w;
            used+=w;if(used==f)return f;
        }
    if(!used)h[x]=-1;
    return used;
}
void dinic(){while(bfs())ans+=dfs(s,inf);}

int main()
{ 
    n=read(),m=read(),s=read(),t=read();
    rep(i,1,m){
        ll u=read(),v=read(),w=read();
        e[++cnt]=(edge){v,u,w,w,last[u]};last[u]=cnt;
        e[++cnt]=(edge){u,v,0,-w,last[v]};last[v]=cnt;
    }
    dinic();
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define inf 1000000000
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxm=1e6+6;
int S,T,ans,n,m,k,cnt=1,que[maxm],d[maxm],last[maxm];
bool inq[maxm];
struct edge{int to,next,v,c;}e[maxm<<2];

void insert(int u,int v,int w,int c){
    e[++cnt]=(edge){v,last[u],w,c};last[u]=cnt;
    e[++cnt]=(edge){u,last[v],0,-c};last[v]=cnt;
}

bool spfa(int S,int T)
{
    mem(inq,0);
    int head=0,tail=1,now;
    rep(i,0,n)d[i]=inf;
    que[0]=T;d[T]=0;inq[T]=1;
    while(head<tail){
        now=que[head++];
        reg(now)
            if(e[i^1].v&&d[now]-e[i].c<d[e[i].to]){
                d[e[i].to]=d[now]-e[i].c;
                if(!inq[e[i].to])inq[e[i].to]=1,que[tail++]=e[i].to;
        }
        inq[now]=0;
    }
    if(d[S]!=inf)return 1;else return 0;
}

int dfs(int x,int f)
{
    if(x==T)return f;
    int used=0,w;inq[x]=1;
    reg(x)
        if(!inq[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to]){
            w=dfs(e[i].to,min(e[i].v,f-used));
            if(w)ans+=w*e[i].c,e[i].v-=w,e[i^1].v+=w,used+=w;
            if(used==f)return f;
        }
    return used;
}

void zkw()
{
    int flow=0;
    while(spfa(S,T)){
        inq[T]=1;
        while(inq[T]){mem(inq,0);flow+=dfs(S,inf);}
    }
    cout<<flow<<' '<<ans<<endl;
}

int main()
{
    n=read(),m=read(),S=read(),T=read();
    rep(i,1,m){
        int u=read(),v=read(),w=read(),c=read();
        insert(u,v,w,c);
    }
    zkw();
    return 0;
}

const int maxn=1e6+6;
int n,a[maxn],pos;
int find(){
    int i=1,j=2,k;
    while(i<=n&&j<=n){
        k=1;while(k<=n&&a[i+k]==a[j+k])k++;
        if(k==n+1)return i;
        if(a[i+k]>a[j+k])i+=k;else j+=k;
        if(i==j)j++;
    }
    return min(i,j);
}
int main()
{
    n=read();
    rep(i,1,n)a[i+n]=a[i]=read();
    pos=find();
    rep(i,1,n-1)printf("%d ",a[i+pos]);printf("%d\n",a[n+pos-1]);
    return 0;
}

    n=read();
    scanf("%s",st+1);
    int j=0;
    rep(i,2,n){
        while(st[j+1]!=st[i]&&j)j=fail[j];
        if(st[j+1]==st[i])j++;
        fail[i]=j;
    }

void manacher(){
    int Max=0,id;
    rep(i,1,n){
        if(Max>=i)p[i]=min(Max-i,p[2*id-i]);else p[i]=0;
        while(ch[i+p[i]+1]==ch[i-p[i]])p[i]++;
        if(p[i]+i>Max)Max=p[i]+i,id=i;
    }
}

const int maxn=3e5+6;
char a[10006][36];
int son[maxn],trie[maxn][27],n,id;
void insert(char st[]){
    int k,now=0,len=strlen(st+1);
    rep(i,1,len){
        k=st[i]-'a';
        if(!trie[now][k])trie[now][k]=++id;
        now=trie[now][k];
        son[now]++;
    }
}
void ask(char st[]){
    int k,now=0,len=strlen(st+1);
    rep(i,1,len){
        if(son[now]==1)break;
        k=st[i]-'a';
        printf("%c",st[i]);
        now=trie[now][k];
    }
}

const int maxn=5e5+6;
char st[56],m[1000006];
int T,n,id,ans,trie[maxn][27],que[maxn],point[maxn],danger[maxn];
bool mark[maxn];
void insert(char st[]){
	int now=1,len=strlen(st+1),k;
	rep(i,1,len){
		k=st[i]-'a'+1;
		if(!trie[now][k])trie[now][k]=++id;
		now=trie[now][k];
	}
	danger[now]++;
}
void acmach(){
	int head=0,tail=1,now;
	que[0]=1;point[1]=0;
	while(head<tail){
		now=que[head++];
		rep(i,1,26){
			if(!trie[now][i])continue;
			int k=point[now];while(!trie[k][i])k=point[k];
			point[trie[now][i]]=trie[k][i];que[tail++]=trie[now][i];
		}
	}
}
void solve(){
	int now=1,len=strlen(m+1);
	rep(i,1,len){
		mark[now]=1;
		int k=m[i]-'a'+1;
		while(!trie[now][k])now=point[now];
		now=trie[now][k];
		if(!mark[now])
			for(int j=now;j;j=point[j])ans+=danger[j],danger[j]=0;
	}
	printf("%d\n",ans);
}
void clear(){
	rep(i,1,id){
	    point[i]=danger[i]=mark[i]=0;
		rep(j,1,26)trie[i][j]=0;
	}
}

const int maxn=2e5+6;
int len,a[maxn],h[maxn],v[maxn],sa[2][maxn],rank[2][maxn],p,q,k;
char st[maxn];
void Pre(){
	len=strlen(st+1);
	rep(i,1,len)a[i]=st[i]-'a'+1;
}
void calsa(int sa[maxn],int rank[maxn],int SA[maxn],int Rank[maxn]){
	rep(i,1,len)v[rank[sa[i]]]=i;
	dep(i,len,1)
		if(sa[i]>k)SA[v[rank[sa[i]-k]]--]=sa[i]-k;
	rep(i,len-k+1,len)SA[v[rank[i]]--]=i;
	rep(i,1,len)Rank[SA[i]]=Rank[SA[i-1]]+(rank[SA[i]]!=rank[SA[i-1]]||rank[SA[i]+k]!=rank[SA[i-1]+k]);
}
void work(){
	p=0,q=1,k=1;
	rep(i,1,len)v[a[i]]++;
	rep(i,1,30)v[i]+=v[i-1];
	rep(i,1,len)sa[p][v[a[i]]--]=i;
	rep(i,1,len)rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
	while(k<len){
		calsa(sa[p],rank[p],sa[q],rank[q]);
		swap(p,q);k<<=1;
	}
}
void geth(){
	k=0;
	rep(i,1,len)
		if(rank[p][i]==1)h[rank[p][i]]=0;
		else{
			int j=sa[p][rank[p][i]-1];
			while(a[i+k]==a[j+k])k++;
			h[rank[p][i]]=k;if(k>0)k--;
		}
}
int main()
{
	scanf("%s",st+1);
	Pre();
	work();
	geth();
	rep(i,1,len)printf("%d ",sa[p][i]);
	printf("\n");
	rep(i,1,len)printf("%d ",h[i]);
	return 0;
}

int n,top;double ans;
const int maxn=5006;
struct P{int x,y;}p[maxn],s[maxn];
inline P operator-(P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline ll operator*(P a,P b){return a.x*b.y-a.y*b.x;}
inline ll dis(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline bool operator<(P a,P b){
    ll t=(a-p[1])*(b-p[1]);
    if(t==0)return dis(p[1],a)<dis(p[1],b);else return t>0;
}
void graham(){
    int t=1;
    rep(i,2,n)
        if(p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x))t=i;//找纵坐标最小的点 
    swap(p[1],p[t]);
    sort(p+2,p+n+1);//将剩下的点排序 
    s[++top]=p[1];s[++top]=p[2];
    rep(i,3,n){
        while((s[top]-s[top-1])*(p[i]-s[top-1])<=0)top--;
        s[++top]=p[i];
    }
    s[top+1]=p[1];
    rep(i,1,top)ans+=sqrt(dis(s[i],s[i+1]));
}

const int maxn=2e3+6;
int n,top;
struct P{double x,y;}p[maxn],s[maxn];
inline P operator-(P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline double operator*(P a,P b){return a.x*b.y-a.y*b.x;}
inline double dis(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline bool operator<(P a,P b){
    double t=(a-p[1])*(b-p[1]);
    if(t==0)return dis(a,p[1])<dis(b,p[1]);else return t<0;
}
void graham(){
    int t=1;
    rep(i,2,n)
        if(p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x))t=i; 
    swap(p[1],p[t]);sort(p+2,p+n+1);
    s[++top]=p[1];s[++top]=p[2];
    rep(i,3,n){
        while(top>1&&((p[i]-s[top-1])*(s[top]-s[top-1]))<=0)top--;
        s[++top]=p[i];
    }
    s[top+1]=p[1];
}
inline double RC(){
    double ans=0;int a,b;
    rep(i,1,top){
        a=i%top+1,b=(i+2)%top+1;
        rep(j,i+2,top){
            while(a%top+1!=j&&(s[j]-s[i])*(s[a+1]-s[i])>(s[j]-s[i])*(s[a]-s[i]))a=a%top+1;
            while(b%top+1!=i&&(s[b+1]-s[i])*(s[j]-s[i])>(s[b]-s[i])*(s[j]-s[i]))b=b%top+1;
            ans=max((s[j]-s[i])*(s[a]-s[i])+(s[b]-s[i])*(s[j]-s[i]),ans);
        }
    }
    return ans;
}

const int maxn=1e5+6;
int n,top,ans[maxn];
struct node{
    int p,v,id;
    friend double Inter(node a,node b){return (double)(a.p-b.p)/(b.v-a.v);}
    friend bool operator<(node a,node b){return a.v!=b.v?a.v<b.v:a.p<b.p;}
}c[maxn],que[maxn];
inline bool jud(node a,node b,node t){return Inter(a,b)>Inter(a,t);}
~~~
    que[++top]=c[1];ans[1]=c[1].id;
    rep(i,2,n){
        while(top>=1&&(Inter(que[top],c[i])<-eps))top--;
        while(top>=2&&jud(que[top-1],que[top],c[i]))top--;
        que[++top]=c[i],ans[top]=c[i].id;
    } 

const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
const int Std[5][5]=\{\{1,1,1,1,1},{0,1,1,1,1},{0,0,2,1,1},{0,0,0,0,1},{0,0,0,0,0\}\}\;
bool flag=0;int T,Map[5][5],x,y,f;
char ch;
inline bool eva(int g){
	int s=0;
	rep(i,0,4)
		rep(j,0,4)
			if(Map[i][j]!=Std[i][j]){s++;if(s+g>f)return 0;}//预估函数值s
	return 1;
}
void idsearch(int g,int x,int y){
	if(g==f){if(check())flag=1;return;}//判断是否符合条件 
	if(flag==1)return;
	rep(i,0,7){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<0||nx>4||ny<0||ny>4)continue;
		swap(Map[x][y],Map[nx][ny]);
		if(eva(g))idsearch(g+1,nx,ny);//判断是否继续搜索 
		swap(Map[x][y],Map[nx][ny]);
	}
}

int main()
{
~~~~~~
		rep(i,1,15){//答案有一定限制
			f=i;//迭代加深总值f
			idsearch(0,x,y);
			if(flag){cout<<f<<endl;break;}
		}
		if(!flag)cout<<"-1"<<endl;
~~~~~~
}

const int maxn=2006;  
int n,m,a[maxn][maxn],h[maxn][maxn],l[maxn][maxn];  
int r[maxn][maxn],ans1=0,ans2=0;  
  
int main()  
{  
    scanf("%d%d",&n,&m);  
    rep(i,1,n)  
       rep(j,1,m){  
               scanf("%d",&a[i][j]);  
               if(i==1)h[i][j]=1;  
               else if(a[i][j]!=a[i-1][j])h[i][j]=h[i-1][j]+1;  
               else h[i][j]=1;  
           }  
    rep(i,1,n){  
        rep(j,1,m){  
            l[i][j]=j;  
            while(l[i][j]>1&&h[i][l[i][j]-1]>=h[i][j]&&a[i][l[i][j]]!=a[i][l[i][j]-1])  
            l[i][j]=l[i][l[i][j]-1];  
        }  
        dep(j,m,1){  
            r[i][j]=j;  
            while(r[i][j]<n&&h[i][r[i][j]+1]>=h[i][j]&&a[i][r[i][j]]!=a[i][r[i][j]+1])  
            r[i][j]=r[i][r[i][j]+1];  
        }  
        rep(j,1,m){  
            int temp=r[i][j]-l[i][j]+1;  
            ans2=max(ans2,temp*h[i][j]);  
            ans1=max(ans1,min(temp,h[i][j])*min(temp,h[i][j]));  
        }  
    }  
    printf("%d\n%d\n",ans1,ans2);  
    return 0;  
}  

int lca(int x,int y)  
{  
    if(deep[x]<deep[y])swap(x,y);  
    int t=deep[x]-deep[y];  
    rep(i,0,10)  
        if((1<<i)&t)x=fa[x][i];  
    dep(i,10,0)  
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];  
    if(x==y)return x;  
    else return fa[x][0];  
}  

const int maxn=6e4+6;
int n,m,t,blo,belong[maxn],a[maxn],ans[maxn],re;
unsigned short cnt[1<<26]; 
char s[maxn];

struct ask{int l,r,pos;}q[maxn];
inline bool cmp(ask a,ask b){
	return belong[a.l]^belong[b.l]?belong[a.l]<belong[b.l]:belong[a.l]&1?a.r<b.r:a.r>b.r;
} 
void insert(int x){
	rep(i,0,t-1)re+=cnt[x^(1<<i)];
	re+=cnt[x]++;
}
void erase(int x){
	rep(i,0,t-1)re-=cnt[x^(1<<i)];
	re-=--cnt[x];
}
int main()
{
	n=read(),m=read();scanf("%s",s+1);
	rep(i,1,n)t=max(t,s[i]-'a'+1);
	blo=n/sqrt(m*2/3);
	rep(i,1,n)belong[i]=(i-1)/blo,a[i]=a[i-1]^(1ll<<s[i]-'a');
	rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].pos=i;
	sort(q+1,q+1+m,cmp);
	for(int i=1,l=1,r=0;i<=m;i++){
		while(l>q[i].l)insert(a[--l]);
		while(r<q[i].r)insert(a[++r]);
		while(l<q[i].l)erase(a[l++]);
		while(r>q[i].r)erase(a[r--]);
		insert(a[l-1]);
		ans[q[i].pos]=re;
		erase(a[l-1]);
	}
	rep(i,1,m)cout<<ans[i]<<endl;
	return 0;
}

int main()
{
    ax=read(),ay=read(),bx=read(),by=read();
    cx=read(),cy=read(),dx=read(),dy=read();
    p=read(),q=read(),r=read();
    double lx=ax,ly=ay,rx=bx,ry=by,x1,y1,x2,y2,t1,t2;
    while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){
        x1=lx+(rx-lx)/3,y1=ly+(ry-ly)/3;
        x2=lx+(rx-lx)/3*2,y2=ly+(ry-ly)/3*2;
        t1=cal(x1,y1),t2=cal(x2,y2);
        if(t1>t2)lx=x1,ly=y1;else rx=x2,ry=y2;
    }
    printf("%.2lf\n",cal(lx,ly));
    return 0; 
}