#include<bits/stdc++.h>
#define M 80005
using namespace std;
int n,m,t,f[M],siz[M],rt[M],fa[M][20],dep[M],cnt,a[M],b[M];
struct Tree{int l,r,sm;}tree[M*290];
vector<int> e[M];
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
void merge(int x,int y){
	x=find(x);y=find(y);
	siz[x]+=siz[y],f[y]=x;
}
void add(int &p,int ji,int l,int r,int wei){
	p=++cnt;
	tree[p]=tree[ji];++tree[p].sm;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(wei<=mid) add(tree[p].l,tree[ji].l,l,mid,wei);
	else add(tree[p].r,tree[ji].r,mid+1,r,wei);
}
void build(int u,int v){
	add(rt[v],rt[u],1,m,a[v]);
	fa[v][0]=u;dep[v]=dep[u]+1;
	for(int i=0;i<16;++i) fa[v][i+1]=fa[fa[v][i]][i];
}
void dfs(int u){
	for(auto v:e[u]) if(v!=fa[u][0])
		build(u,v),dfs(v);
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=dep[x]-dep[y];i;i-=(i&(-i))) x=fa[x][__builtin_ctz(i)];
	if(x==y) return y;
	for(int i=16;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];	
}
int query(int a,int b,int c,int d,int l,int r,int sm){
	if(l==r) return l;
	int mid=(l+r)>>1;
	int gu=(tree[tree[a].l].sm+tree[tree[b].l].sm-tree[tree[c].l].sm-tree[tree[d].l].sm);
	if(gu<sm)
		return query(tree[a].r,tree[b].r,tree[c].r,tree[d].r,mid+1,r,sm-gu);
	else return query(tree[a].l,tree[b].l,tree[c].l,tree[d].l,l,mid,sm);
}
int main(){
	freopen("P3302_3.in","r",stdin);
	freopen("P3302.out","w",stdout);
	scanf("%*d%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;++i){ scanf("%d",&a[i]);b[i]=a[i];}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
		merge(u,v);
	}
	sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	for(int i=1;i<=n;++i) f[i]=i,siz[i]=1;
	for(int i=1;i<=n;++i) if(!rt[i]) build(0,i),dfs(i);
	char op;int x,y,k,lst=0,L;
	while(t--){
		scanf(" %c%d%d",&op,&x,&y);x^=lst,y^=lst;
		if(op=='Q'){
			scanf("%d",&k);k^=lst;
			L=lca(x,y);
			printf("%d\n",lst=b[query(rt[x],rt[y],rt[L],rt[fa[L][0]],1,m,k)]);
		}
		else{
			if(siz[find(x)]<siz[find(y)]) swap(x,y);
			merge(x,y);
			e[x].push_back(y);e[y].push_back(x);
			build(x,y);dfs(y);
		}
	}
	return 0;
}