LCT

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,T,a[N],vl[N],s[N][2],f[N],tg[N],st[N],top;
void up(int x){vl[x]=vl[s[x][0]]^vl[s[x][1]]^a[x];}
void rev(int x){swap(s[x][0],s[x][1]),tg[x]^=1;}
void down(int x){if(tg[x]) rev(s[x][0]),rev(s[x][1]),tg[x]=0;}
int get(int x){return s[f[x]][1]==x;}
int nrt(int x){return s[f[x]][0]==x||s[f[x]][1]==x;}
void rot(int x){
	int y=f[x],z=f[y],k=get(x);
	if(nrt(y)) s[z][get(y)]=x;
	f[x]=z;
	s[y][k]=s[x][k^1],f[s[x][k^1]]=y;
	s[x][k^1]=y,f[y]=x;
	up(y),up(x);
}
void upd(int x){
	st[top=1]=x;
	while(nrt(x)) st[++top]=x=f[x];
	while(top) down(st[top--]);
}
void splay(int x){
	upd(x);
	for(int y;y=f[x],nrt(x);rot(x))
	if(nrt(y)) rot(get(x)^get(y)?x:y);
}
void access(int x){for(int y=0;x;x=f[y=x]) splay(x),s[x][1]=y,up(x);}
int find(int x){
	access(x),splay(x),down(x);
	while(s[x][0]) x=s[x][0],down(x);
	splay(x);
	return x;
}
void make(int x){access(x),splay(x),rev(x);}
void split(int x,int y){make(x),access(y),splay(y);}
void link(int x,int y){make(x);if(find(y)^x) f[x]=y;}
void cut(int x,int y){
	make(x);
	if(find(y)==x&&f[y]==x&&!s[y][0]) f[y]=s[x][0]=0,up(x);
}
int main(){
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),vl[i]=a[i];
	int op,x,y;
	while(T--){
		scanf("%d%d%d",&op,&x,&y);
		if(op==0) split(x,y),printf("%d\n",vl[y]);
		else if(op==1) link(x,y);
		else if(op==2) cut(x,y);
		else if(op==3) splay(x),a[x]=y,up(x);
	}
}