#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 160001

#define D 15

using namespace std;

char ch[];

int t,x,y,z;

int n,m,qq,tot,cut,ans,father[MAXN],dis[MAXN];

int head[MAXN],size[MAXN],deep[MAXN],root[MAXN],s[MAXN],fa[MAXN][D+];

struct edge {

    int v,next;

} e[MAXN*];

struct data {

    int lc,rc,size;

} tree[MAXN*];

struct node {

    int x,o;

} a[MAXN];

void add(int u,int v) {

    e[++cut].v=v;

    e[cut].next=head[u];

    head[u]=cut;

}

bool cmp(const node &x,const node &y) {

    if(x.x==y.x) return x.o<y.o;

    return x.x<y.x;

}

int find(int x) {

    return x!=father[x]?father[x]=find(father[x]):x;

}

void change(int &k,int last,int l,int r,int x) {

    k=++tot;

    tree[k].lc=tree[last].lc,tree[k].rc=tree[last].rc;

    tree[k].size=tree[last].size+;

    if(l==r) return ;

    int mid=(l+r)>>;

    if(x<=mid) change(tree[k].lc,tree[last].lc,l,mid,x);

    else change(tree[k].rc,tree[last].rc,mid+,r,x);

    return ;

}

int query(int L,int R,int lc,int falc,int l,int r,int k) {

    if(l==r) return l;

    int sum=tree[tree[R].lc].size+tree[tree[L].lc].size-

            tree[tree[lc].lc].size-tree[tree[falc].lc].size;

    int mid=l+r>>;

    if(sum>=k)

        return query(tree[L].lc,tree[R].lc,tree[lc].lc,tree[falc].lc,l,mid,k);

    else return

            query(tree[L].rc,tree[R].rc,tree[lc].rc,tree[falc].rc,mid+,r,k-sum);

}

void dfs1(int u,int f) {

    size[u]=;

    fa[u][]=f;

    int p=lower_bound(s+,s+n+,a[u].x)-s;

    change(root[u],root[f],,n,p);

    for(int i=head[u]; i; i=e[i].next) {

        int v=e[i].v;

        if(v!=f) deep[v]=deep[u]+,dfs1(v,u),size[u]+=size[v];

    }

    return ;

}

void get_father() {

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

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

            fa[i][j]=fa[fa[i][j-]][j-];

    return ;

}

int get_same(int u,int x) {

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

        if(x&(<<i)) u=fa[u][i];

    return u;

}

int lca(int x,int y) {

    if(deep[x]<deep[y]) swap(x,y);

    x=get_same(x,deep[x]-deep[y]);

    if(x==y) return x;

    for(int i=D; i>=; i--)

        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

    return fa[x][];

}

void slovequery(int x,int y,int k) {

    int lc=lca(x,y);

    ans=query(root[x],root[y],root[lc],root[fa[lc][]],,n,k);

    ans=s[ans];

    printf("%d\n",ans);

    return ;

}

void slove(int u,int f) {

    fa[u][]=f;

    deep[u]=deep[f]+;

    int p=lower_bound(s+,s+n+,a[u].x)-s;

    change(root[u],root[f],,n,p);

    for(int i=; i<=D; i++) fa[u][i]=fa[fa[u][i-]][i-];

    for(int i=head[u]; i; i=e[i].next) {

        int v=e[i].v;

        if(v!=f) slove(v,u);

    }

    return ;

}

void union_(int x,int y) {

    int l1=find(x),l2=find(y);

    if(size[l1]>size[l2]) swap(l1,l2),swap(x,y);

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

    father[l1]=l2,size[l1]+=size[l2];

    slove(x,y);

    return ;

}

int main() {

    cin>>t>>n;

    cin>>m>>qq;

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

        father[i]=i,cin>>a[i].x,a[i].o=i,s[i]=a[i].x;

    sort(s+,s+n+);

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

        cin>>x>>y,add(x,y),add(y,x);

        int l1=find(x),l2=find(y);

        father[l2]=l1;

    }

    for(int i=; i<=n; i++) if(!fa[i][]) dfs1(i,);

    get_father();

    while(qq--) {

        scanf("%s",ch);

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

            cin>>x>>y>>z;

            x^=ans,y^=ans,z^=ans;

            slovequery(x,y,z);

        } else {

            cin>>x>>y;

            x^=ans,y^=ans;

            union_(x,y);

        }

    }

    return ;

}