1 #include<bits/stdc++.h>

  2 using namespace std;

  3 const int N=1e5+5;

  4 int n,m,a[N],w[N];

  5 struct node{

  6     int fa,lc,rc,rv;

  7     #define lc(x) t[x].lc

  8     #define rc(x) t[x].rc

  9     #define fa(x) t[x].fa

 10     #define rv(x) t[x].rv

 11 }t[N];

 12

 13 void up(int x){

 14     w[x]=a[x]^w[lc(x)]^w[rc(x)];

 15 }

 16

 17 bool isr(int x)//isroot

 18 {

 19     return lc(fa(x))!=x&&rc(fa(x))!=x;

 20 }

 21 bool wrt(int x){

 22     return rc(fa(x))==x;

 23 }

 24

 25 void rev(int x){//做标记

 26     if(!x) return;

 27     swap(lc(x),rc(x));

 28     rv(x)^=1;

 29 }

 30

 31 void down(int x){//下传标记

 32     if(rv(x)){

 33         rev(lc(x)),rev(rc(x));

 34     }

 35     rv(x)=0;

 36 }

 37

 38 void rot(int x){//旋转

 39     int y=fa(x),z=fa(y),b=(lc(y)==x)?rc(x):lc(x);

 40     if(z&&!isr(y)) (lc(z)==y?lc(z):rc(z))=x;

 41     fa(x)=z,fa(y)=x;

 42     if(b) fa(b)=y;

 43     if(lc(y)==x) rc(x)=y,lc(y)=b;

 44     else lc(x)=y,rc(y)=b;

 45     up(y),up(x);

 46 }

 47

 48 void path(int x){//根到节点上的点都下传标记

 49     if(!isr(x)) path(fa(x));

 50     down(x);

 51 }

 52

 53 void spl(int x){//splay

 54     path(x);

 55     while(!isr(x)){

 56         if(!isr(fa(x))) wrt(x)==wrt(fa(x))?rot(fa(x)):rot(x);

 57         rot(x);

 58     }

 59 }

 60

 61 void acs(int x){

 62     for(int y=0;x;y=x,x=fa(x)){

 63         spl(x),rc(x)=y,up(x);

 64     }

 65 }

 66

 67 void mrt(int x){//makeroot

 68     acs(x),spl(x),rev(x);

 69 }

 70

 71 int fnd(int x){//findroot

 72     acs(x),spl(x),down(x);

 73     while(lc(x)) x=lc(x),down(x);

 74     spl(x);return x;

 75 }

 76

 77 void lk(int x,int y){//link

 78     mrt(x);

 79     if(fnd(y)==x) return ;

 80     fa(x)=y;

 81 }

 82

 83 void cut(int x,int y){//删边

 84     mrt(x),acs(y),spl(y);

 85     if(lc(y)!=x) return ;

 86     lc(y)=fa(x)=0;

 87 }

 88

 89 int main(){

 90     scanf("%d%d",&n,&m);

 91     for(int i=1;i<=n;i++){

 92         scanf("%d",&a[i]),w[i]=a[i];

 93     }

 94     for(int i=1;i<=m;i++){

 95         int o,x,y;

 96         scanf("%d%d%d",&o,&x,&y);

 97         if(o==0){

 98             mrt(x),acs(y),spl(y);//提取x到y的路径

 99             cout<<w[y]<<endl;

100         }

101         if(o==1) lk(x,y);

102         if(o==2) cut(x,y);

103         if(o==3) acs(x),spl(x),a[x]=y,up(x);

104     }

105     return 0;

106 }