代码：

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int val,ch[2],fa,lazy,sum;
}tree[500005];
int sz,stk[500005],topp;
inline void pushdown(int nod)
{
	if(tree[nod].lazy)
	{
		tree[nod].lazy^=1;
		tree[tree[nod].ch[0]].lazy^=1;
		tree[tree[nod].ch[1]].lazy^=1;
		swap(tree[tree[nod].ch[0]].ch[0],tree[tree[nod].ch[0]].ch[1]);
		swap(tree[tree[nod].ch[1]].ch[0],tree[tree[nod].ch[1]].ch[1]);
	}
}
inline void update(int nod)
{
	tree[nod].sum=tree[nod].val^tree[tree[nod].ch[0]].sum^tree[tree[nod].ch[1]].sum;
}
inline bool root(int x)
{
	if(x==tree[tree[x].fa].ch[0])return true;
	if(x==tree[tree[x].fa].ch[1])return true;
	return false;
}
inline bool get(int p){return p==tree[tree[p].fa].ch[1];}
inline void rotate(int nod)
{
	int f=tree[nod].fa,z=tree[f].fa,ck=get(nod),sec=tree[nod].ch[1-ck],getf=get(f);
	tree[sec].fa=f;
	tree[f].ch[ck]=sec;
	tree[nod].fa=z;
	if(root(f))tree[z].ch[getf]=nod;
	tree[f].fa=nod;
	tree[nod].ch[1-ck]=f;
	update(f);
	update(nod);
}
inline void splay(int x)
{
	int y=x;topp=0;
	while(root(y))stk[++topp]=y,y=tree[y].fa;
	stk[++topp]=y;
	while(topp)
	{
		pushdown(stk[topp]);
		topp--;
	}
	while(root(x))
	{
		int f=tree[x].fa;
		if(root(f))
			if(get(x)!=get(f))rotate(f);
			else rotate(x);
		rotate(x);
	}
	update(x);
}
inline void access(int x)
{
	for(int y = 0;x;y=x,x=tree[x].fa)
		splay(x),tree[x].ch[1]=y,update(x);
}
inline void makeroot(int x)
{
	access(x);
	splay(x);
	tree[x].lazy^=1;
	swap(tree[x].ch[0],tree[x].ch[1]);
}
inline int findroot(int x)
{
	access(x);
	splay(x);
	while(tree[x].ch[0])pushdown(x),x=tree[x].ch[0];
	access(x);
	splay(x);
	return x;
}
inline void split(int x,int y)
{
	makeroot(x);
	access(y);
	splay(y);
}
inline void link(int x,int y)
{
	makeroot(x);
	if(x!=findroot(y))tree[x].fa=y;
}
inline void cut(int x,int y)
{
	makeroot(x);
	if(x!=findroot(y))return;
	if(tree[y].fa!=x||tree[y].ch[0])return;
	tree[x].ch[1]=0,tree[y].fa=0;
	update(x);
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 1;i <=n;i++)scanf("%d",&tree[i].val),tree[i].sum=tree[i].val;
	for(int i = 1;i <=m;i++)
	{
		int type,x,y;
		scanf("%d %d %d",&type,&x,&y);
		if(type==0)split(x,y),printf("%d\n",tree[y].sum);
		else if(type==1)link(x,y);
		else if(type==2)cut(x,y);
		else if(type==3)splay(x),tree[x].val=y;
	}
	return 0;
}