强制在线资瓷连边的树上$K$大（小）值。
静态树上$K$大值可以用主席树，结合$LCA$加加减减就行。
要求连边，可以启发式合并主席树。其实也可以说重构主席树。维护一下每个点所在的树的$size$，连接两点，选择$size$较小的连到较大的上去，即重新$dfs$一遍。
由于每个点合并一次后$size$至少翻倍，所以最多被合并$logn$次。重构一个点主席树复杂度为$O(logn)$，总复杂度$O(nlog^2n)$。
维护$size$珂以用并查集。因为要改变树的形态，树剖$LCA$不能用了，珂以用倍增$LCA$或者$LCT$求$LCA$。（蒟蒻以前一直用的树剖$LCA$，结果倍增写假了调了两天$QAQ$）
空间上可以重复利用之前的点，不过蒟蒻懒得写想省时间所以没有，所以单点重构主席树要开$O(logn)$个节点，空间复杂度$O(nlog^2n)$。
细节：值域很大，需要离散化
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 80005
#define inf 0x3f3f3f3f
#define pn putchar('\n')
#define px(x) putchar(x)
#define ps putchar(' ')
#define pd puts("======================")
#define pj puts("++++++++++++++++++++++")
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int h[maxn],num,F[maxn],siz[maxn];
//F是并查集
struct edge{
int pre,to;
}e[maxn<<1];
inline void add(int from,int to){
e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
int find(int x){
if(F[x]==x)return x;
return F[x]=find(F[x]);
}
int n,len,dis[maxn],a[maxn],root[maxn],fa[maxn][32],lg[maxn],deep[maxn];
//dis是离散化数组
struct Chairman_Tree{
int dat[maxn*400],ls[maxn*400],rs[maxn*400],cnt;
#define ls(x) ls[x]
#define rs(x) rs[x]
void build(int poi,int ne,int ol){
int l=1,r=len;
while(l<r){
dat[ne]=dat[ol]+1;
int mid=l+r>>1;
if(poi<=mid)rs(ne)=rs(ol),ol=ls(ol),ne=ls(ne)=++cnt,r=mid;
else ls(ne)=ls(ol),ol=rs(ol),ne=rs(ne)=++cnt,l=mid+1;
}
dat[ne]=dat[ol]+1;
}//主席树重构
int ask(int x,int y,int lc,int fl,int k){
//lc是lca，fl为lca的父亲
int l=1,r=len;
while(l<r){
int mid=l+r>>1,sum=dat[ls(x)]+dat[ls(y)]-dat[ls(lc)]-dat[ls(fl)];
if(sum>=k)x=ls(x),y=ls(y),lc=ls(lc),fl=ls(fl),r=mid;
else x=rs(x),y=rs(y),lc=rs(lc),fl=rs(fl),l=mid+1,k-=sum;
}
return dis[l];
}//查询
}ct;
int lca(int x,int y){
if(deep[x]<deep[y])swap(x,y);
while(deep[x]>deep[y])x=fa[x][lg[deep[x]-deep[y]]-1];
if(x==y)return x;
for(register int i=lg[deep[x]];i>=0;--i)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}//倍增lca
void dfs(int node,int f){
deep[node]=deep[f]+1;
root[node]=++ct.cnt;
ct.build(a[node],root[node],root[f]);
fa[node][0]=f;
int top=lg[deep[node]];
for(register int i=1;i<=top;++i)
fa[node][i]=fa[fa[node][i-1]][i-1];
for(register int i=h[node];i;i=e[i].pre){
int x=e[i].to;
if(x!=f)siz[node]+=siz[x],dfs(x,node);
}
}
void merge(int x,int y){
add(x,y),add(y,x);
int u=find(x),v=find(y);
if(siz[u]>siz[v])swap(x,y),swap(u,v);
siz[v]+=siz[u];
dfs(x,y);
}
int spget(){
char ch=getchar();
while(ch!='Q'&&ch!='L')ch=getchar();
return ch=='Q';
}//获取字符的
int main(){
read();
n=read();
int m=read(),t=read();
for(register int i=1;i<=n;++i)
F[i]=i,a[i]=dis[i]=read(),lg[i]=lg[i-1]+(1<<lg[i-1]==i);
sort(dis+1,dis+1+n);
len=unique(dis+1,dis+1+n)-dis-1;
for(register int i=1;i<=n;++i)
a[i]=lower_bound(dis+1,dis+1+len,a[i])-dis;
//离散化
for(register int i=1;i<=m;++i){
int a=read(),b=read();
add(a,b),add(b,a);
}
for(register int i=1;i<=n;++i)
if(!deep[i])dfs(i,0);
for(register int i=1;i<=n;++i)
if(fa[i][0])F[i]=fa[i][0];
//初始化并查集
for(register int i=1;i<=n;++i)
++siz[find(i)];
//初始化size
int ans=0;
for(register int i=1;i<=t;++i){
int s=spget(),x=read()^ans,y=read()^ans;
if(s){
int k=read()^ans,l=lca(x,y);
printf("%d\n",ans=ct.ask(root[x],root[y],root[l],root[fa[l][0]],k));
}
else merge(x,y);
}
}
