1 #include<cstdio> 2 #include<algorithm> 3 #define N 500010 4 #define rg register 5 #define ls (c[u][0]) 6 #define rs (c[u][1]) 7 using namespace std; 8 int n,m,x,y,opt,top,val[N],c[N][2],fa[N],xr[N],st[N],rev[N]; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 inline bool isroot(int u){ 16 return c[fa[u]][0]!=u&&c[fa[u]][1]!=u; 17 } 18 inline bool which(int u){ 19 return c[fa[u]][1]==u; 20 } 21 inline void pushup(int u){ 22 xr[u]=xr[ls]^xr[rs]^val[u]; 23 } 24 inline void pushdown(int u){ 25 rev[ls]^=1; rev[rs]^=1; rev[u]=0; swap(ls,rs); 26 } 27 void rotate(int u){ 28 int f=fa[u],gf=fa[f],wh=which(u); 29 if(!isroot(f)) c[gf][which(f)]=u; 30 fa[u]=gf; fa[f]=u; fa[c[u][wh^1]]=f; 31 c[f][wh]=c[u][wh^1]; c[u][wh^1]=f; 32 pushup(f); pushup(u); 33 } 34 void splay(int u){ 35 st[top=1]=u; 36 for(rg int i=u;!isroot(i);i=fa[i]) st[++top]=fa[i]; 37 for(rg int i=top;i;i--) if(rev[st[i]]) pushdown(st[i]); 38 while(!isroot(u)){ 39 if(!isroot(fa[u])) rotate(which(u)==which(fa[u])?fa[u]:u); 40 rotate(u); 41 } 42 } 43 inline void access(int u){ 44 for(rg int son=0;u;son=u,u=fa[u]) splay(u),c[u][1]=son,pushup(u); 45 } 46 inline void makeroot(int u){ 47 access(u); splay(u); rev[u]^=1; 48 } 49 int find(int u){ 50 access(u); splay(u); 51 while(ls) u=ls; return u; 52 } 53 void split(int x,int y){ 54 makeroot(x); access(y); splay(y); 55 } 56 void cut(int x,int y){ 57 split(x,y); bool goright=0; 58 int t=c[y][0]; 59 while(c[t][1]) t=c[t][1],goright=1; 60 if(t==x&&goright) c[fa[t]][1]=0,fa[x]=0; 61 if(t==x&&(!goright)) c[y][0]=0,fa[x]=0; 62 } 63 void link(int x,int y){ 64 makeroot(x); fa[x]=y; 65 } 66 int main(){ 67 n=read(); m=read(); 68 for(rg int i=1;i<=n;i++) val[i]=xr[i]=read(); 69 while(m--){ 70 opt=read(); x=read(); y=read(); 71 if(opt==0) split(x,y),printf("%d ",xr[y]); 72 if(opt==1) if(find(x)!=find(y))link(x,y); 73 if(opt==2) if(find(x)==find(y)) cut(x,y); 74 if(opt==3) access(x),splay(x),val[x]=y,pushup(x); 75 } 76 return 0; 77 }