RT，从这学的

#include <iostream>
#include <random>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
std::mt19937 rdna(0x383494);
std::uniform_real_distribution<> RAnd_(0, 1);
#define Rnd() RAnd_(rdna)
namespace LCT{ // }{{{
struct Node{
	Node *ls, *rs, *fa;
	int lisiz, alsiz; // light_siz, all_siz
	int val, sum;
	bool rev;
	Node();
} nil_, *nil = &nil_;
Node::Node(){ fa = ls = rs = nil; }
bool isrs(Node *x){ return x == x->fa->rs; }
bool nroot(Node *x){ return x == x->fa->ls || x == x->fa->rs; }
void flip(Node *x){ x->rev ^= 1; }
void pushup(Node *x){ 
	x->sum = x->ls->sum ^ x->rs->sum ^ x->val; 
	x->alsiz = 1 + x->ls->alsiz + x->rs->alsiz + x->lisiz;
}
void pushuuuu(Node *x){
	pushup(x);
	if(nroot(x)) pushuuuu(x->fa);
}
void pushdown(Node *x){
	if(!x->rev) return;
	if(x->ls != nil) flip(x->ls);
	if(x->rs != nil) flip(x->rs);
	std::swap(x->ls, x->rs);
}
void pushdddd(Node *x){
	if(nroot(x)) pushdddd(x->fa);
	pushdown(x);
}
Node *merge(Node *sm, Node *bg){
	if(sm == nil || bg == nil) return sm == nil ? bg : sm;
	if(Rnd()*(sm->alsiz + bg->alsiz) < sm->alsiz){
		pushdown(sm);
		sm->rs = merge(sm->rs, bg);
		bg->fa = sm;
		pushup(sm);
		return sm;
	} else {
		pushdown(bg);
		bg->ls = merge(sm, bg->ls);
		sm->fa = bg;
		pushup(bg);
		return bg;
	}
}
Node* splitl(Node *x, Node *&sm, Node *&bg){ // [0, x]:sm, (x, r): bg, return light-fa
	pushdddd(x);
	Node *f = x->fa;
	sm = x, bg = x->rs;
	x->rs = nil;
	pushup(x);
	while(nroot(x)){
		if(isrs(x)){
			f->ls = bg;
			bg->fa = f;
			bg = f;
		} else {
			f->rs = sm;
			sm->fa = f;
			sm = f;
		}
		pushup(f);
		x = f;
		f = f->fa;
	}
	//sm->fa = bg->fa = nil;
	return f;
}
Node *access(Node *x){ // return root of x
	Node *ret = nil;
	while(x != nil){
		Node *sm, *bg;
		Node *top = splitl(x, sm, bg);
		if(bg != nil) bg->fa = x;
		x->lisiz -= bg->alsiz;
		x->lisiz += ret->alsiz;
		pushuuuu(x);
		ret = merge(sm, ret);
		x = top;
		ret->fa = x;
	}
	return ret;
}
Node *getroot(Node *x){
	while(nroot(x)) x=x->fa;
	return x;
}
void mkroot(Node *x){ flip(access(x)); }
void link(Node *x, Node *y){
	mkroot(x);
	Node *r = getroot(x);
	r->fa = y;
	y->lisiz += r->alsiz;
	access(y);
	pushuuuu(y);
}
void cut(Node *x, Node *y){
	mkroot(x);
	access(y);
	Node *tmp1, *tmp2;
	splitl(x, tmp1, tmp2);
}
int query(Node *x, Node *y){
	mkroot(x);
	Node *rt = access(y);
	return rt->sum;
}
} // {}}}
namespace m{ // }{{{
constexpr int N = 1e5, M = 3e5;
using std::cin;
using std::cout;
using namespace LCT;
Node nds[N];
int in, im;
void work(){
	cin >> in >> im;
	UP(i, 0, in) cin >> nds[i].val;
	UP(i, 0, im){
		int op, x, y;
		cin >> op >> x >> y;
		x--, y--;
		if(op == 0){
			cout << query(nds+x, nds+y) << '\n';
		} else if(op == 1){
			link(nds+x, nds+y);
		} else if(op == 2){
			cut(nds+x, nds+y);
		} else {
			y++;
			nds[x].val = y;
			pushup(nds+x);
		}
	}
}
} // {}}}
int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); m::work(); return 0;}