1 //BZOJ 3282  2 //by Cydiater  3 //2016.9.16  4 #include <iostream>  5 #include <cstdio>  6 #include <cstring>  7 #include <algorithm>  8 #include <queue>  9 #include <map> 10 #include <ctime> 11 #include <cmath> 12 #include <iomanip> 13 #include <cstdlib> 14 #include <string> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22     char ch=getchar();int x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 int N,M,op,nodea,nodeb,node,num,q[MAXN],top=0; 28 struct Tree{ 29     int son[2],v,Xor,fa,tag; 30 }t[MAXN]; 31 namespace solution{ 32     inline bool get(int node){return t[t[node].fa].son[1]==node;} 33     inline bool isroot(int node){return t[t[node].fa].son[1]!=node&&t[t[node].fa].son[0]!=node;} 34     inline void updata(int node){ 35         if(node){ 36             t[node].Xor=t[node].v; 37             if(t[node].son[0])t[node].Xor^=t[t[node].son[0]].Xor; 38             if(t[node].son[1])t[node].Xor^=t[t[node].son[1]].Xor; 39         } 40     } 41     inline void downit(int node){ 42         if(t[node].tag){ 43             t[t[node].son[0]].tag^=1;t[t[node].son[1]].tag^=1; 44             swap(t[node].son[1],t[node].son[0]); 45             t[node].tag=0; 46         } 47     } 48     void rotate(int node){ 49         int old=t[node].fa,oldf=t[old].fa,which=get(node); 50         if(!isroot(old))t[oldf].son[t[oldf].son[1]==old]=node; 51         t[old].son[which]=t[node].son[which^1];t[t[old].son[which]].fa=old; 52         t[node].son[which^1]=old;t[old].fa=node;t[node].fa=oldf; 53         updata(old);updata(node); 54     } 55     void splay(int node){ 56         top=0;q[++top]=node; 57         for(int i=node;!isroot(i);i=t[i].fa)q[++top]=t[i].fa; 58         down(i,top,1)downit(q[i]); 59         while(!isroot(node)){ 60             int old=t[node].fa,oldf=t[old].fa; 61             if(!isroot(old))rotate(get(node)==get(old)?old:node); 62             rotate(node); 63         } 64     } 65     void access(int node){ 66         int tmp=0; 67         while(node){ 68             splay(node); 69             t[node].son[1]=tmp; 70             updata(node);tmp=node; 71             node=t[node].fa; 72         } 73     } 74     void Reverse(int node){access(node);splay(node);t[node].tag^=1;} 75     void Link(int noda,int nodb){Reverse(noda);t[noda].fa=nodb;} 76     void Cut(int noda,int nodb){Reverse(noda);access(nodb);splay(nodb);if(t[nodb].son[0]==nodea)t[nodb].son[0]=t[noda].fa=0;} 77     void LCA(int noda,int nodb){Reverse(nodb);access(noda);splay(noda);} 78     int find(int node){ 79         access(node);splay(node); 80         int tmp=node; 81         while(t[tmp].son[0])tmp=t[tmp].son[0]; 82         return tmp; 83     } 84     void change(int node,int num){ 85         access(node);splay(node);//down lazy_tag 86         t[node].v=num;updata(node); 87     } 88     //Link-Cut-Tree 89     void init(){ 90         N=read();M=read(); 91         up(i,1,N){ 92             t[i].v=read(); 93             t[i].son[0]=t[i].son[1]=0; 94             t[i].Xor=t[i].v;t[i].fa=0; 95         } 96     } 97     void slove(){ 98         while(M--){ 99             op=read();100             if(op==0){101                 nodea=read();nodeb=read();102                 LCA(nodea,nodeb);printf("%d\n",t[nodea].Xor);103             }104             if(op==1){105                 nodea=read();nodeb=read();106                 if(find(nodea)==find(nodeb))continue;107                 Link(nodea,nodeb);108             }109             if(op==2){110                 nodea=read();nodeb=read();111                 if(find(nodea)!=find(nodeb))continue;112                 Cut(nodea,nodeb);113             }114             if(op==3){115                 node=read();num=read();116                 change(node,num);117             }118         }119     }120 }121 int main(){122     //freopen("input.in","r",stdin);123     using namespace solution;124     init();125     slove();126     return 0;127 }