#include<cstdio>

#include<cmath>

#include<cstring>

#include<cctype>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=8e4+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct tree{

    int l,r,sum;

}tr[N*];

struct node{

    int to,nxt;

}edge[N*];

int a[N],b[N],rt[N],pool,n,m;

int dep[N],anc[N][],son[N];

int cnt,head[N],fa[N],vis[N],tot;

inline void add(int u,int v){

    edge[++cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt;

}

inline void insert(int y,int &x,int l,int r,int p){

    tr[x=++pool]=tr[y];tr[x].sum++;

    if(l==r)return;

    int mid=(l+r)>>;

    if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p);

    else insert(tr[y].r,tr[x].r,mid+,r,p);

}

inline int query(int nl,int nr,int nm,int nfm,int l,int r,int k){

    if(l==r)return l;

    int delta=tr[tr[nl].l].sum+tr[tr[nr].l].sum-tr[tr[nm].l].sum-tr[tr[nfm].l].sum;

    int mid=(l+r)>>;

    if(delta>=k)return query(tr[nl].l,tr[nr].l,tr[nm].l,tr[nfm].l,l,mid,k);

    else return query(tr[nl].r,tr[nr].r,tr[nm].r,tr[nfm].r,mid+,r,k-delta);

}

inline void LSH(){

    sort(b+,b+m+);

    m=unique(b+,b+m+)-b-;

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

    a[i]=lower_bound(b+,b+m+,a[i])-b;

    }

    return;

}

inline int LCA(int i,int j){

    if(dep[i]<dep[j])swap(i,j);

    for(int k=;k>=;k--){

        if(dep[anc[i][k]]>=dep[j])i=anc[i][k];

    }

    if(i==j)return i;

    for(int k=;k>=;k--){

        if(anc[i][k]!=anc[j][k])i=anc[i][k],j=anc[j][k];

    }

    return anc[i][];

}

int find(int x){

    if(fa[x]==x)return x;

    return fa[x]=find(fa[x]);

}

void dfs(int u,int f,int root){

    anc[u][]=f;

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

    anc[u][k]=anc[anc[u][k-]][k-];

    son[root]++;dep[u]=dep[f]+;fa[u]=root;vis[u]=;

    insert(rt[f],rt[u],,m,a[u]);

    for(int i=head[u];i;i=edge[i].nxt){

        int v=edge[i].to;

        if(v!=f)dfs(v,u,root);

    }

    return;

}

int main(){

    read();

    n=read();int e=read(),T=read(),last=;

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

    a[i]=b[++m]=read(),fa[i]=i;

    LSH();

    for(int i=;i<=e;i++){

    int x=read(),y=read();

    add(x,y);add(y,x);

    }

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

    if(!vis[i]){

        dfs(i,,++tot);fa[tot]=tot;

    }

    for(int i=;i<=T;i++){

    char ch=getchar();

        while(ch!='Q'&&ch!='L')ch=getchar();

    if(ch=='Q'){

        int x=read()^last,y=read()^last,k=read()^last;

        int t=LCA(x,y),ft=anc[t][];

        printf("%d\n",last=b[query(rt[x],rt[y],rt[t],rt[ft],,m,k)]);

    }else{

        int x=read()^last,y=read()^last;

        add(x,y);add(y,x);

        int u=find(x),v=find(y);

        if(son[u]<son[v]){

        swap(u,v);

        swap(x,y);

        }

        dfs(y,x,u);

    }

    }

    return ;

}