第一组样例输出2\n1，第二组基本不对，但数量级是对的。

#include<bits/stdc++.h>
using namespace std;
#define reg register
extern "C" {
namespace io{
#define BUFS 1000000
	static char in[BUFS], *p = in, *pp = in, out[BUFS], *q = out, ch[20], *t = ch;
#define gc() (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
	inline int read() {
		reg int x = 0; reg char ch, f = 0;
		while (!isdigit(ch = gc())) f |= ch == '-';
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return f ? -x : x;
	}
	inline void write(int x, char sp) {
		x || (*q++ = 48), x < 0 && (*q++ = '-', x = -x);
		while (x) *t++ = x % 10 + 48, x /= 10;
		while (t != ch) *q++ = *--t;
		*q++ = sp;
	}
	inline void flush() {fwrite(out, 1, q - out, stdout);}
}}
#define rd io :: read
#define wt io :: write
const int N = 500001;
struct Node {
	int val, res; bool tag; Node *fa, *ch[2];
	Node() {}
	Node(int val, int res, bool tag, Node *fa, Node *ls, Node *rs) : val(val), res(res), tag(tag), fa(fa) {ch[0] = ls, ch[1] = rs;}
}*null, spl[N];
inline bool nroot(Node *x) {x -> fa -> ch[0] == x || x -> fa -> ch[1] == x;}
inline void pushup(Node *x) {x -> res = x -> ch[0] -> res ^ x -> val ^ x -> ch[1] -> res;}
inline void rev(Node *x) {x -> tag ^= 1, swap(x -> ch[0], x -> ch[1]);}
inline void pushdown(Node *x) {
	x -> tag && (
		x -> ch[0] != null && (rev(x -> ch[0]), 0),
		x -> ch[1] != null && (rev(x -> ch[1]), 0),
		x -> tag = 0
	);
}
inline void rotate(Node *x) {
	reg Node *y = x -> fa, *z = y -> fa; reg int k = y -> ch[1] == x;
	y -> ch[k] = x -> ch[k ^ 1], x -> ch[k ^ 1] -> fa = y;
	x -> ch[k ^ 1] = y, y -> fa = x,
	nroot(y) && (z -> ch[z -> ch[1] == y] = x, 0), x -> fa =z;
	pushup(y), pushup(x);
}
inline void pushall(Node *x) {
	nroot(x) && x -> fa != null && (pushall(x -> fa), 0);
	pushdown(x);
}
inline void splay(Node *x) {
	pushall(x);
	for (reg Node *y, *z; nroot(x); rotate(x))
		y = x -> fa, z = y -> fa,
		nroot(y) && (rotate((z -> ch[0] == y) ^ (y -> ch[0] == x)? x : y), 0);
	pushup(x);
}
inline void access(Node *x) {
	for (reg Node *y = null; x != null; y = x, x = x -> fa)
		splay(x), x -> ch[1] = y, pushup(x);
}
inline void makeroot(Node *x) {access(x), splay(x), rev(x);}
inline Node* findroot(Node *x) {
	access(x), splay(x);
	for (; x -> ch[0] != null; x = x -> ch[0]) pushdown(x);
	splay(x);
	return x;
}
inline void split(Node *x, Node *y) {makeroot(x), access(y), splay(y);}
inline void link(Node *x, Node *y) {makeroot(x); findroot(y) != x && (x -> fa = y);}
inline void cut(Node *x, Node *y) {
	makeroot(x);
	findroot(y) == x && y -> fa == x && y -> ch[0] == null && (y -> fa = x -> ch[1] = 0, pushup(x), 0);
}
int n, m;
int main() {
	null = &(spl[0] = Node(0, 0, 0, 0, 0, 0));
	n = rd(), m = rd();
	for (reg int i = 1; i <= n; ++i) spl[i].val = rd(), spl[i].ch[0] = spl[i].ch[1] = spl[i].fa = null;
	for (reg int op, x, y; m; --m) {
		op = rd(), x = rd(), y = rd();
		switch(op) {
			case 0 :
				split(spl + x, spl + y), wt(spl[y].res, '\n');
				break;
			case 1 :
				link(spl + x, spl + y);
				break;
			case 2 :
				cut(spl + x, spl + y);
				break;
			case 3 :
				splay(spl + x), spl[x].val = y;
				break;
		}
	}io :: flush();
	return 0;
}