/*平常这种题很常见的思路就是求出dfs序来，然后每次查询的时候就是在主席树上查询 x+y-lca-fa[lca] 的值就行了。 但是这个题要动态的给森林中加边，还是强制在线的，所以就需要考虑换一种方法来维护这个东西。 首先先dfs出每棵树来，然后对于link操作，可以启发式合并两个主席树。这里我们把主席树维护的dfs序变成维护每个点到根的这条路径。所里link的时候假设我们要把x合到y上，那么我们就边dfs x 这棵树，边用当前点的fa作为历史状态的root来更新当前点的root就行了。求lca的fa数组和deep数组在dfs的时候动态维护就行了。 复杂度： O(nlog2n) */#include<cstdio>#include<iostream>using namespace std;const int N=1e5+5;const int M=2e7+5;const int inf=1e9;int n,m,T,sz,num,ans,val[N],dep[N],siz[N],belong[N],fa[N][20];bool flag[N];struct edge{int u,v,next;}e[N<<1];int tot,head[N];int root[N],R[N],sum[M],ls[M],rs[M];inline int read(){    int x=0;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x;}inline void add(int x,int y){    e[++tot].v=y;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].next=head[y];head[y]=tot;}void insert(int &k,int last,int l,int r,int pos){    k=++sz;    sum[k]=sum[last]+1;    if(l==r) return ;    ls[k]=ls[last];    rs[k]=rs[last];    int mid=l+r>>1;    if(pos<=mid) insert(ls[k],ls[last],l,mid,pos);    else insert(rs[k],rs[last],mid+1,r,pos);}void dfs(int x,int f,int now){    flag[x]=1;siz[x]=1;belong[x]=now;    for(int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];    insert(root[x],root[f],1,inf,val[x]);    for(int i=head[x];i;i=e[i].next){        if(e[i].v!=f){            fa[e[i].v][0]=x;            dep[e[i].v]=dep[x]+1;            dfs(e[i].v,x,now);            siz[x]+=siz[e[i].v];        }    }}inline int lca(int a,int b){    if(dep[a]<dep[b]) swap(a,b);    int t=dep[a]-dep[b];    for(int i=0;i<20;i++){        if(t&(1<<i)){            a=fa[a][i];        }    }    if(a==b) return a;    for(int i=19;~i;i--){        if(fa[a][i]!=fa[b][i]){            a=fa[a][i];            b=fa[b][i];        }    }    return fa[a][0];}int query(int l,int r,int x1,int x2,int x3,int x4,int pos){    if(l==r) return l;    int now=sum[ls[x1]]+sum[ls[x2]]-sum[ls[x3]]-sum[ls[x4]];    int mid=l+r>>1;    if(now>=pos) return query(l,mid,ls[x1],ls[x2],ls[x3],ls[x4],pos);    return query(mid+1,r,rs[x1],rs[x2],rs[x3],rs[x4],pos-now);}int main(){    freopen("forest.in","r",stdin);    freopen("forest.out","w",stdout);    T=read();n=read();m=read();T=read();    for(int i=1;i<=n;i++) val[i]=read();    for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y);    for(int i=1;i<=n;i++) if(!flag[i]) dfs(i,0,++num),R[num]=i;    for(int x,y,z,anc;T--;){        char ch;        for(ch=getchar();ch!=‘Q‘&&ch!=‘L‘;ch=getchar());        x=read();y=read();        x^=ans;y^=ans;        if(ch==‘Q‘){            z=read();z^=ans;            anc=lca(x,y);            ans=query(1,inf,root[x],root[y],root[anc],root[fa[anc][0]],z);            printf("%d\n",ans);        }        else{            if(siz[R[belong[x]]]>siz[R[belong[y]]]) swap(x,y);            add(y,x);            fa[x][0]=y;            siz[R[belong[y]]]+=siz[R[belong[x]]];            dep[x]=dep[y]+1;            dfs(x,y,belong[y]);        }    }    return 0;}/*10#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;#define setfire(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);#define fre(name) freopen(#name".txt","r",stdin);#ifdef WIN32#define LL "%lld"#else#define LL "%I64d"#endifconst int N=1e5+5;int cas,n,m,t,ans,val[N],tv[N],stack[N],prev[N];bool vis[N];struct edge{int v,next;}e[N<<1];int tot,head[N];char s[50];inline int read(){    int x=0;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x;}inline void add(int x,int y){    e[++tot].v=y;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].next=head[y];head[y]=tot;}inline void bfs(int S,int T){    int top=1;stack[top]=S;    memset(vis,0,(n+2));    memset(prev,0,(n+2)<<2);    while(top){        int x=stack[top--];        for(int i=head[x];i;i=e[i].next){            if(!vis[e[i].v]){                vis[e[i].v]=1;                prev[e[i].v]=x;                if(e[i].v==T) return ;                stack[++top]=e[i].v;            }        }    }}inline void calc(int S,int T,int rk){    tv[0]=0;    for(int i=T;i!=S;i=prev[i]) tv[++tv[0]]=val[i];tv[++tv[0]]=val[S];    nth_element(tv+1,tv+rk,tv+tv[0]+1);    printf("%d\n",ans=tv[rk]);}void init(){    tot=0;    memset(head,0,(n+2)<<2);}int main(){    freopen("forest.in","r",stdin);    freopen("forest.out","w",stdout);    //for(cas=read();init(),cas--;){        cas=read();        n=read();m=read();t=read();        for(int i=1;i<=n;i++) val[i]=read();        for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y);        for(int x,y,z;t--;){            scanf("%s",s);            if(s[0]==‘Q‘){                x=read();y=read();z=read();                x^=ans;y^=ans;z^=ans;                bfs(x,y);                calc(x,y,z);            }            else{                x=read();y=read();                x^=ans;y^=ans;                add(x,y);            }        }//    }    return 0;} */