#include<bits/stdc++.h>
#define N 500005
using namespace std;

bool la[N];
int n,m,op,x,y;
int ch[N][5],val[N],num[N],sz[N],fa[N],pre[N]; 
int st[N],top;
struct node{int x,y;};

inline int read(){
	int x=0,w=0; char c=0;
	while(!isdigit(c)){w|=c=='-';c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return w?-x:x;
}

inline bool check(int p){
	if(!fa[p]) return 1;
	if(ch[fa[p]][0]!=p&&ch[fa[p]][1]!=p) return 1;
	return 0;
}

inline void pushup(int p){
	sz[p]=sz[ch[p][0]]^sz[ch[p][1]]^val[p];
	if(ch[p][0]) fa[ch[p][0]]=p;
	if(ch[p][1]) fa[ch[p][1]]=p;
} 

inline void pushdown(int p){
	if(la[p]){
		la[p]=0;
		swap(ch[p][0],ch[p][1]);
		if(ch[p][0]) la[ch[p][0]]^=1;
		if(ch[p][1]) la[ch[p][1]]^=1;
	}
}

inline int merge(int x,int y){
	if(!x||!y) return x|y;
	else{
		if(num[x]<num[y]){
			pushdown(x);
			ch[x][1]=merge(ch[x][1],y);
			pushup(x);
			return x;
		}else{
			pushdown(y);
			ch[y][0]=merge(x,ch[y][0]);
			pushup(y);
			return y;
		}
	} 
}

inline int findr(int p){
	top=0;
	while(!check(p)){
		st[++top]=(ch[fa[p]][0]==p);
		p=fa[p];
	} 
	return p;
}

inline int findl(int p){
	p=findr(p);
	pushdown(p);
	while(ch[p][0]){
		p=ch[p][0];
		pushdown(p);
	}
	return p;
}

inline node split(int p){
	node ans;
	if(!top){
		pushdown(p);
		ans={p,ch[p][1]};
		ch[p][1]=0;
		pushup(p);
		return ans;
	}
	bool f=st[top--]^la[p];
	pushdown(p);
	if(f){
		ans=split(ch[p][0]);
		ch[p][0]=ans.y;
		pushup(p);
		return (node){ans.x,p};
	}else{
		ans=split(ch[p][1]);
		ch[p][1]=ans.x;
		pushup(p);
		return (node){p,ans.y};
	}
}

inline int access(int p){
	int las=0;
	while(p){
		node tmp=split(findr(p));
		pre[findl(las)]=0;
		las=merge(tmp.x,las);
		pre[findl(tmp.y)]=p;
		p=pre[findl(las)];
	}
	return las;
}

inline int root(int p){
	return findl(access(p));
}

inline int changer(int p){
	la[access(p)]^=1;
}

inline void link(int x,int y){
	changer(x);
	pre[x]=y;
}

inline void cut(int x,int y){
	changer(x);
	access(y);
	access(x);
	pre[y]=0;
}

inline int query(int x,int y){
	changer(x);
	access(y);
	node tmp=split(findr(y));
	int ans=sz[tmp.x];
	merge(tmp.x,tmp.y);
	return ans;
}

inline void change(int p,int k){
	changer(p);
	node tmp=split(findr(p));
	val[p]=k;
	merge(tmp.x,tmp.y);
}

signed main(){
	srand(time(0));
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		sz[i]=val[i]=read();
		num[i]=rand();
	}
	while(m--){
		op=read(),x=read(),y=read();
		if(op==0) printf("%d\n",query(x,y));
		if(op==1&&root(x)!=root(y)) link(x,y);
		if(op==2) cut(x,y);
		if(op==3) change(x,y); 
	}
	return 0;
}