#include <cstdio>

#include <algorithm>

#define N 80010

using namespace std;

int n , w[N] , a[N] , ref[N] , head[N] , to[N << 1] , next[N << 1] , cnt , fa[N][20] , deep[N] , log[N] , bl[N] , si[N];

int ls[N << 8] , rs[N << 8] , sum[N << 8] , root[N] , tot;

char str[5];

void add(int x , int y)

{

	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;

}

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

{

	if(!y) y = ++tot;

	sum[y] = sum[x] + 1;

	if(l == r) return;

	int mid = (l + r) >> 1;

	if(p <= mid) rs[y] = rs[x] , insert(p , l , mid , ls[x] , ls[y]);

	else ls[y] = ls[x] , insert(p , mid + 1 , r , rs[x] , rs[y]);

}

int query(int p , int l , int r , int a , int b , int c , int d)

{

	if(l == r) return ref[l];

	int mid = (l + r) >> 1;

	if(sum[ls[a]] + sum[ls[b]] - sum[ls[c]] - sum[ls[d]] >= p) return query(p , l , mid , ls[a] , ls[b] , ls[c] , ls[d]);

	else return query(p - sum[ls[a]] - sum[ls[b]] + sum[ls[c]] + sum[ls[d]] , mid + 1 , r , rs[a] , rs[b] , rs[c] , rs[d]);

}

void dfs(int x , int r)

{

	int i;

	bl[x] = r , si[r] ++ ;

	insert(w[x] , 1 , n , root[fa[x][0]] , root[x]);

	for(i = 1 ; i <= log[deep[x]] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1];

	for(i = head[x] ; i ; i = next[i])

		if(to[i] != fa[x][0])

			fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i] , r);

}

int lca(int x , int y)

{

	int i;

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

	for(i = log[deep[x] - deep[y]] ; i >= 0 ; i -- )

		if(deep[x] - deep[y] >= (1 << i))

			x = fa[x][i];

	for(i = log[deep[x]] ; i >= 0 ; i -- )

		if(deep[x] >= (1 << i) && fa[x][i] != fa[y][i])

			x = fa[x][i] , y = fa[y][i];

	return x == y ? x : fa[x][0];

}

int main()

{

	int m , q , i , t , x , y , z , last = 0;

	scanf("%*d%d%d%d" , &n , &m , &q);

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , a[i] = w[i];

	sort(a + 1 , a + n + 1);

	for(i = 1 ; i <= n ; i ++ ) t = w[i] , w[i] = lower_bound(a + 1 , a + n + 1 , w[i]) - a , ref[w[i]] = t;

	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);

	log[0] = -1;

	for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;

	for(i = 1 ; i <= n ; i ++ ) if(!fa[i][0]) dfs(i , i);

	while(q -- )

	{

		scanf("%s%d%d" , str , &x , &y) , x ^= last , y ^= last;

		if(str[0] == 'Q')

		{

			scanf("%d" , &z) , z ^= last , t = lca(x , y);

			printf("%d\n" , last = query(z , 1 , n , root[x] , root[y] , root[t] , root[fa[t][0]]));

		}

		else

		{

			if(si[bl[x]] < si[bl[y]]) swap(x , y);

			fa[y][0] = x , deep[y] = deep[x] + 1 , dfs(y , bl[x]) , add(x , y) , add(y , x);

		}

	}

	return 0;

}