RE #3，#6.

#include<bits/stdc++.h>
using namespace std;
#define N 160010
inline int read(){
	int x=0;char op=getchar();
	while(!isdigit(op))op=getchar();
	while(isdigit(op)){x=(x<<1)+(x<<3)+(op^48);op=getchar();}
	return x;
}
void print(int x){
	if(x>=10)print(x/10);
	putchar(x-x/10*10+'0');
}
struct Edge{
	int ne,to;
	#define ne(x) edge[x].ne
	#define to(x) edge[x].to
}edge[N<<1];
struct HJT{
	int son[2],sum;
	#define son(x,y) tree[x].son[y]
	#define sum(x) tree[x].sum
}tree[N*40];
int head[N],idx=1,n,m,q,a,b,c,Fa[N],size[N],dep[N],fa[N][20],w[N],ww[N],un;
int root[N],cnt,testcase;
char op;
inline void add(int from,int to){
	ne(++idx)=head[from];
	to(idx)=to;
	head[from]=idx;
}
int get_fa(int x){
	if(x==Fa[x])return x;
	return Fa[x]=get_fa(Fa[x]);
}
void change(int &p,int pre,int l,int r,int x){
	p=++cnt;tree[p]=tree[pre];
	if(l==r){
		sum(p)++;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(son(p,0),son(pre,0),l,mid,x);
	else change(son(p,1),son(pre,1),mid+1,r,x);
	sum(p)=sum(son(p,0))+sum(son(p,1));
}
int ask(int x,int y,int l,int r,int k){
	if(l==r)return l;
	int mid=(l+r)>>1;
	int d=sum(son(y,0))-sum(son(x,0));
	if(k<=d)return ask(son(x,0),son(y,0),l,mid,k);
	else return ask(son(x,1),son(y,1),mid+1,r,k-d);
}
int query(int x,int y,int xx,int yy,int l,int r,int k){
	if(l==r)return l;
	int mid=(l+r)>>1;
	int d=sum(son(y,0))-sum(son(x,0))+(sum(son(yy,0))-sum(son(xx,0)));
	if(k>d)return query(son(x,1),son(y,1),son(xx,1),son(yy,1),mid+1,r,k-d);
	else return query(son(x,0),son(y,0),son(xx,0),son(yy,0),l,mid,k);
}
void dfs(int u,int FA){
	fa[u][0]=FA;dep[u]=dep[FA]+1;
	for(int i=1;i<=19;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
	change(root[u],root[FA],1,un,w[u]);
	for(int i=head[u];i;i=ne(i)){
		int y=to(i);
		if(y==FA)continue;
		dfs(y,u);
	}
}
int LCA(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int i=19;~i;--i){
		if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
	}
	if(x==y)return x;
	for(int i=19;~i;--i){
		if(fa[x][i]&&fa[y][i]&&fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//ios::sync_with_stdio(false);
	//cin.tie(0),cout.tie(0);
	testcase=read();
	n=read();m=read();q=read();
	for(int i=1;i<=n;++i)w[i]=ww[i]=read(),Fa[i]=i,size[i]=1;
	sort(ww+1,ww+n+1);
	un=unique(ww+1,ww+n+1)-ww-1;
	for(int i=1;i<=n;++i)w[i]=lower_bound(ww+1,ww+un+1,w[i])-ww;
	for(int i=1;i<=m;++i){
		a=read();b=read();
		add(a,b);add(b,a);
		int x=get_fa(a),y=get_fa(b);
		Fa[x]=y;
		size[y]+=size[x];
	}
	for(int i=1;i<=n;++i){
		if(i==Fa[i]){
			dfs(i,0);
		}
	}
	int lastans=0;
	while(q--){
		op=getchar();while(op!='Q'&&op!='L')op=getchar();
		if(op=='Q'){
			a=read()^lastans;b=read()^lastans;c=read()^lastans;
			if(a==b){
				lastans=ww[w[a]];
				print(lastans);
				puts("");
				continue;
			}
			int lca=LCA(a,b);
			lastans=ww[query(root[fa[lca][0]],root[a],root[lca],root[b],1,un,c)];
			print(lastans);
			puts("");
		}else{
			a=read()^lastans;b=read()^lastans;
			add(a,b);add(b,a);
			int x=get_fa(a),y=get_fa(b);
			if(size[x]>size[y]){
				Fa[y]=x;
				size[x]+=size[y];
				dfs(b,a);
			}else{
				Fa[x]=y;
				size[y]+=size[x];
				dfs(a,b);
			}
		}
	}
	return 0;
}