#include 
#define print(x,y) write(x),putchar(y)

template 
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while((s=getchar())>'9' || s<'0')
		f |= (s=='-');
	while(s>='0' && s<='9')
		x = (x<<1)+(x<<3)+(s^48),
		s = getchar();
	return f?-x:x;
}

template 
inline void write(T x) {
	static int writ[50],w_tp=0;
	if(x<0) putchar('-'),x=-x;
	do writ[++w_tp]=x-x/10*10,x/=10; while(x);
	while(putchar(writ[w_tp--]^48),w_tp);
}

#include 
using namespace std;

const int maxn = 1e5+5;

int n,m;
struct node {
	bool tag;
	int s,v,son[2],fa;
} t[maxn];

int dir(int o) {
	return (t[t[o].fa].son[1] == o)?1:
		   (t[t[o].fa].son[0] == o)?0:-1;
}

bool isRoot(int o) { 
	return (t[t[o].fa].son[0]^o) &&
		   (t[t[o].fa].son[1]^o);
	/* it can be replaced by dir() */
}

void add(int o,int f,int d) {
	if(o) t[o].fa=f;
	if(~d && f) t[f].son[d]=o;
}

void printNode(int o) {
	int lc=t[o].son[0], rc=t[o].son[1];
	printf("node %d son(%d %d) fa(%d) tag(%d) %d\n",o,lc,rc,t[o].fa,t[o].tag,t[o].s);
}

void pushUp(int o) {
	if(!o) return;
	int lc=t[o].son[0], rc=t[o].son[1];
	t[o].s = t[lc].s^t[rc].s^t[o].v;
}

void rev(int o) {
	if(!o) return;
	swap(t[o].son[0],t[o].son[1]);
	t[o].tag ^= 1;
}

void pushDown(int o) {
	if(!o || !t[o].tag) return;
	rev(t[o].son[0]), rev(t[o].son[1]);
	t[o].tag=0;
}

void rotate(int o) {
	int f=t[o].fa, ff=t[f].fa;
	int d=dir(o), fd=dir(f);
	add(t[o].son[d^1],f,d);
	add(f,o,d^1);
	add(o,ff,fd);
	pushUp(f), pushUp(o);
}

/*
	为啥必须在 splay() 中先从上到下 pushDown() 呢？
	朴素 splay 中，实际不需要在 rotate()/splay() 中 pushDown()，这是因为 find() 已经将所有的标记下放
	朴素 splay 中，对于某个子树，如果暂时没有翻转（假设祖先有翻转标记），而对其进行操作，实际上也是正确的
	但对于 LCT，在操作子树时，必须时时保证左右儿子的信息正确
*/

void pushAll(int o) {
	static int stk[maxn], tp;
	stk[tp=1] = o;
	while(!isRoot(o)) stk[++tp] = (o=t[o].fa);
	while(tp) pushDown(stk[tp--]);
}

void splay(int o) {
	pushAll(o); 
	for(int f; f=t[o].fa, !isRoot(o); rotate(o))
		if(!isRoot(f)) rotate(dir(f)==dir(o)?f:o);
	// pushUp(o); // is it necessary??
}

void access(int o) {
	for(int ch=0; o; o=t[ch=o].fa)
		splay(o), t[o].son[1]=ch, pushUp(o); 
	/* splay o to guarantee that the dfs order of u(the original value of o) is the biggest */
}

void makeRoot(int o) {
	access(o); splay(o);
	rev(o); // reverse the DFS order of the splay that o be at
	/* but do not change the others */
	/* because the edges between them are virtual, the tags won't be pushdown */
}

int findRoot(int o) {
	access(o); splay(o);
	while(t[o].son[0]) o=t[o].son[0];
	splay(o); // splay the real root to the aux-root
	return o;
}

/* after access(), x might not be the aux-root */
/* so we just splay y to the aux-root */

void split(int x,int y) {
	makeRoot(x); 
	access(y); splay(y);
}

void link(int x,int y) {
	makeRoot(x);
	if(findRoot(y)^x) t[x].fa=y;
}

void cut(int x,int y) {
	makeRoot(x);
	if(findRoot(y)==x && t[y].fa==x && !t[y].son[0])
		t[y].fa=t[x].son[1]=0, pushUp(x);
}

int main() {
	n=read(9), m=read(9);
	for(int i=1;i<=n;++i)
		t[i].s=t[i].v=read(9);
	int opt,x,y;
	while(m --) {
		opt=read(9);
		x=read(9), y=read(9);
		if(!opt) split(x,y), print(t[y].s,'\n');
		if(opt==1) link(x,y);
		if(opt==2) cut(x,y);
		if(opt==3) splay(x), t[x].s=t[x].v=y;
	}
	return 0;
}

int getThat(int o) {
	bool isOdd = (t[o].s&1);
	int havi=1e9, ls, rs, adl=0, adr=0, mid=(t[o].s>>1);
	while(o) {
		pushDown(o);
		int lc=t[o].son[0], rc=t[o].son[1];
		ls = t[lc].s+adl, rs = t[rc].s+adr;
		if(ls<=mid && rs<=mid) {
			if(isOdd) { havi=o; break; }
			else havi = min(havi,o);
		}
		if(ls