听灌佬多

#include<bits/stdc++.h>
#define PII pair<int,int>
#define DB double
#define LL long long
#define comp complex<double>
#define int long long
//#define int __int128
//const int mod=1e9+7;
//const int mod=998244353;
const LL inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;
const DB pi=acos(-1);
namespace FastIO{
	inline int read(int mod=0){
		int x=0,f=1;char ch=getchar();
		if(mod==0){while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}}
		else{while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x*10%mod+ch-48)%mod;ch=getchar();}}
		return x*f;}
	inline char cread(){char x;while(x==0||x==' '||x=='\n'||x=='\r')x=getchar();return x;}
	inline void write(int x){if(x<0)putchar('-'),x=-x;if(x==0)return;write(x/10),putchar(x%10+'0');}
}
using namespace FastIO;
using namespace std;
int a[100005];
struct LCT{
	struct Node{
		int ls,rs,fa;
		int val,xr,rv;
	}t[100005];
	void init(int n){
		for(int i=1;i<=n;++i)
			t[i]={0,0,0,a[i],a[i],0};
	}
	inline void pushup(int p){
		t[p].xr=t[t[p].ls].xr^t[t[p].rs].xr^t[p].val;
	}
	inline void pushdn(int p){
		if(!t[p].rv)return;
		t[t[p].ls].rv^=1,t[t[p].rs].rv^=1,t[p].rv^=1;
		swap(t[p].ls,t[p].rs);
	}
	inline bool isroot(int p){
		if(t[t[p].fa].ls!=p&&t[t[p].fa].rs!=p)return 1;
		return 0;
	}
	inline void rotate(int p){
		if(t[t[p].fa].ls==p){
			int q=t[p].fa;
			if(t[t[q].fa].ls==q)t[t[q].fa].ls=p;
			else if(t[t[q].fa].rs==q)t[t[q].fa].rs=p;
			t[p].fa=t[q].fa;
			t[q].ls=t[p].rs,t[t[q].ls].fa=q;
			t[p].rs=q,t[q].fa=p;
			pushup(q),pushup(p);
		}
		else if(t[t[p].fa].rs==p){
			int q=t[p].fa;
			if(t[t[q].fa].ls==q)t[t[q].fa].ls=p;
			else if(t[t[q].fa].rs==q)t[t[q].fa].rs=p;
			t[p].fa=t[q].fa;
			t[q].rs=t[p].ls,t[t[q].rs].fa=q;
			t[p].ls=q,t[q].fa=p;
			pushup(q),pushup(p);
		}
	}
	inline void splay(int p){
		stack<int>st;int tmp=p;st.push(p); 
		while(!isroot(tmp))st.push(tmp=t[tmp].fa);
		while(!st.empty())pushdn(st.top()),st.pop();
		while(!isroot(p)){rotate(p);}
	}
	inline void access(int p){
		int tmp=0;
		while(p){
			splay(p),t[p].rs=tmp;
			pushup(p),tmp=p,p=t[p].fa; 
		}
	}
	inline void makeroot(int x){
		access(x),splay(x),t[x].rv^=1;
	}
	inline int find(int p){
		access(p),splay(p);
		while(t[p].ls)p=t[p].ls;
		return p;
	}
	void split(int x,int y){
		makeroot(x),access(y),splay(y);
	}
	void cut(int x,int y){
		split(x,y);
		if(t[y].ls==x&&!t[x].rs)
			t[y].ls=0,t[x].fa=0;
	}
	void link(int x,int y){
		makeroot(x),t[x].fa=y;
	}
	void print(int n){
		for(int i=1;i<=n;++i){
			printf("%lld :\n",i);
			printf("fa %lld ls %lld rs %lld\nxr %lld val %lld rev %lld\n",t[i].fa,t[i].ls,t[i].rs,t[i].xr,t[i].val,t[i].rv);
		}
	}
}tr;
signed main(){
	int n=read(0),m=read(0);
	for(int i=1;i<=n;++i)a[i]=read(0);
	tr.init(n);
	for(int i=1;i<=m;++i){
		int op=read(0),x=read(0),y=read(0);
		if(op==0){
			tr.split(x,y);
			printf("%lld\n",tr.t[y].xr);
		} 
		if(op==1){
			if(tr.find(x)==tr.find(y))continue;
			tr.link(x,y);
		}
		if(op==2){
			if(tr.find(x)!=tr.find(y))continue;
			tr.cut(x,y);
		}
		if(op==3){
			tr.access(x),tr.splay(x),tr.t[x].val=y,tr.pushup(x);
		}
	}
	return 0;
}