第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。 
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。 
 接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。

对于每一个第一类操作，输出一个非负整数表示答案。

对于第一个操作 Q 8 7 3，此时 lastans=0，所以真实操作为Q 8^0 7^0 3^0，也即Q 8 7 3。点8到点7的路径上一共有5个点，其权值为4 1 1 2 4。这些权值中，第三小的为 2，输出 2，lastans变为2。对于第二个操作 Q 3 5 1 ，此时lastans=2，所以真实操作为Q 3^2 5^2 1^2 ，也即Q 1 7 3。点1到点7的路径上一共有4个点，其权值为 1 1 2 4 。这些权值中，第三小的为2，输出2，lastans变为 2。之后的操作类似。

#include<stdio.h>

#include<string.h>

#define N 80110

#define INF 1000000000

#define mid ((x>>1)+(y>>1)+(x&y&1))

inline void exc(int &x,int &y){

    x^=y;y^=x;x^=y;

}

inline int Rin(){

    int x=,c=getchar(),f=;

    for(;c<||c>;c=getchar())

        if(!(c^))f=-;

    for(;c>&&c<;c=getchar())

        x=(x<<)+(x<<)+c-;

    return x*f;

}

int n,m,T,val[N],jump[N][],dep[N],pb[N],top,ans;

struct st{int f,s;}s[N];

inline int pre(int x){

    while(s[x].f^x)x=s[x].f;

    return x;

}

inline void onion(int x,int y){

    x=pre(x),y=pre(y);

    s[y].f=x,s[x].s+=s[y].s;

}

struct pt{int v;pt *nxt;}

*fst[N],e[N<<],*tot=e;

inline void link(int x,int y){

    *++tot=(pt){y,fst[x]},fst[x]=tot;

    *++tot=(pt){x,fst[y]},fst[y]=tot;

}

struct nt{

    nt *l,*r;

    int s;

}*rt[N],pool[],*C=pool;

inline nt *newnt(nt *_,nt *__,int ___){

    C->l=_;C->r=__;C->s=___;

    return C++;

}

nt *build(nt *p,int x,int y,int k){

    if(!(x^y))return newnt(0x0,0x0,p->s+);

    if(k<=mid)return newnt(build(p->l,x,mid,k),p->r,p->s+);

    return newnt(p->l,build(p->r,mid+,y,k),p->s+);

}

void dfs(int x){

    dep[x]=dep[jump[x][]]+;

    rt[x]=build(rt[jump[x][]],,INF,val[x]);

    for(pt *j=fst[x];j;j=j->nxt)

        if(j->v^jump[x][])

            jump[j->v][]=x,

            dfs(j->v);

}

void dfs(int x,int f){

    pb[++top]=x;

    jump[x][]=f;

    dep[x]=dep[f]+;

    rt[x]=build(rt[f],,INF,val[x]);

    for(pt *j=fst[x];j;j=j->nxt)

        if(j->v^f)dfs(j->v,x);

}

int lca(int x,int y){

    if(dep[x]<dep[y])exc(x,y);

    for(int j=;~j;j--)

        if(dep[jump[x][j]]>=dep[y])

            x=jump[x][j];

    if(!(x^y))return x;

    for(int j=;~j;j--)

        if(jump[x][j]^jump[y][j])

            x=jump[x][j],y=jump[y][j];

    return jump[x][];

}

int secret(nt *p1,nt *p2,nt *p3,nt *p4,int x,int y,int k){

    if(!(x^y))return x;

    int c=p1->l->s+p2->l->s-p3->l->s-p4->l->s;

    if(k<=c)return secret(p1->l,p2->l,p3->l,p4->l,x,mid,k);

    return secret(p1->r,p2->r,p3->r,p4->r,mid+,y,k-c);

}

int feel(int x,int y,int k){

    int t=lca(x,y);

    return secret(rt[x],rt[y],rt[t],rt[jump[t][]],,INF,k);

}

int main(){

    T=Rin(),n=Rin(),m=Rin(),T=Rin();

    for(int i=;i<=n;i++)

        s[i].f=i,s[i].s=;

    for(int i=;i<=n;i++)

        val[i]=Rin();

    for(int x,y;m;m--)

        x=Rin(),y=Rin(),link(x,y),onion(x,y);

    rt[]=newnt(C,C,);

    for(int i=;i<=n;i++)

        if(!jump[i][])

            dfs(i);

    for(int j=;j<=;j++)

        for(int i=;i<=n;i++)

            jump[i][j]=jump[jump[i][j-]][j-];

    char sign[];

    for(int x,y,k;T;T--){

        scanf("%s",sign);

        x=Rin()^ans,y=Rin()^ans;

        if(sign[]=='Q'){

            k=Rin()^ans;

            printf("%d\n",ans=feel(x,y,k));

        }

        else{

            if(s[pre(x)].s>s[pre(y)].s)

                exc(x,y);

            top=;

            dfs(x,y);

            onion(x,y);

            for(int j=;j<=;j++)

                for(int i=;i<=top;i++)

                    jump[pb[i]][j]=jump[jump[pb[i]][j-]][j-];

            link(x,y);

        }

    }

    return ;

}