神秘永无乡。
很典的平衡树题。
写的时候一堆细节。
对于每个连通块维护一个平衡树，然后暴力启发式合并。写的数组版本的，所以合并那里写了一个直接插入节点的，省空间，时间复杂度是一样的。最开始合并的时候想用改根来直接判断对应树，发现平衡树换根就炸了，加了个并查集。一开始写的dfs遍历合并，好像会T，改成了用一个栈。算是第一次成功应用平衡树吧。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define fir first
#define sec second
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=1e5+5;
int n,m,q;
struct node{int sz,cnt,fa,ch[2],val,id;node(){sz=cnt=id=val=fa=ch[0]=ch[1]=0;}};
node t[N<<1];int tot;
struct Splay{int rt;Splay(){rt=0;}int add(int k,int fa,int id){t[++tot].cnt=1;t[tot].sz=1,t[tot].val=k,t[tot].fa=fa,t[tot].id=id;return tot;}void clear(int p){t[p].sz=t[p].cnt=1,t[p].fa=t[p].ch[0]=t[p].ch[1]=0;}void upd(int p){t[p].sz=t[t[p].ch[0]].sz+t[t[p].ch[1]].sz+t[p].cnt;}void rotate(int p){int f=t[p].fa,ff=t[f].fa;int k=(p==t[f].ch[1]),k1=(f==t[ff].ch[1]),s=t[p].ch[k^1];t[f].ch[k]=s;if(s)t[s].fa=f;t[p].ch[k^1]=f,t[f].fa=p;if(ff)t[ff].ch[k1]=p;t[p].fa=ff;if(!ff)rt=p;upd(f),upd(p);}void splay(int p,int g){while(t[p].fa!=g){int f=t[p].fa,ff=t[f].fa;if(ff!=g&&ff)(p==t[f].ch[1])^(f==t[ff].ch[1])?rotate(p):rotate(f);rotate(p);}if(!g)rt=p;}int find(int k){int now=rt,re=0;while(1){if(k>=t[now].val){re+=t[t[now].ch[0]].sz;if(k==t[now].val){splay(now,0);return re+1;}re+=t[now].cnt,now=t[now].ch[1];}else now=t[now].ch[0];if(!now)return re+1;}return re;}void insert(int k,int id){if(!rt){rt=add(k,0,id);return;}int now=rt,fa=0;while(1){if(t[now].val==k){t[now].cnt++,t[now].sz++;if(fa)upd(fa);splay(now,0);return;}fa=now,now=t[now].ch[k>t[now].val];if(!now){now=add(k,fa,id),t[fa].ch[k>t[fa].val]=now;upd(fa),splay(now,0);return;}}}void ins_node(int p){if(!rt){rt=p;return;}int now=rt,fa=0,k=t[p].val;clear(p);while(1){if(t[now].val==k){t[now].cnt++,t[now].sz++;if(fa)upd(fa);splay(now,0);return;}fa=now,now=t[now].ch[k>t[now].val];if(!now){t[fa].ch[k>t[fa].val]=p,t[p].fa=fa;upd(fa),splay(p,0);return;}}}int prev(){int now=t[rt].ch[0];while(t[now].ch[1])now=t[now].ch[1];return now;}void del(int k){find(k);int p=rt;if(!t[rt].ch[0]&&!t[rt].ch[1])rt=0,clear(p);else if(!t[rt].ch[0])rt=t[rt].ch[1],clear(p);else if(!t[rt].ch[1])rt=t[rt].ch[0],clear(p);else{int pr=prev();splay(pr,0);int s=t[p].ch[1];t[pr].ch[1]=s;if(s)t[s].fa=pr;clear(p);}}int kth(int k){int now=rt;if(t[rt].sz<k)return -1;while(k&&now){int lsz=t[t[now].ch[0]].sz,cnt=t[now].cnt;if(k<=lsz)now=t[now].ch[0];else if(k>lsz+cnt)k-=lsz+cnt,now=t[now].ch[1];else return t[now].id;}return -1;}
}T[N];
struct DSU{int fa[N],sz[N],s[N],tp,tot;void init(){for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;}int fd(int x){return fa[x]=((fa[x]^x)?fd(fa[x]):x);}void mg(int a,int b){a=fd(a),b=fd(b);if(a==b)return;if(sz[a]<sz[b])swap(a,b);sz[a]+=sz[b],fa[b]=a;tot=1,tp=1,s[1]=T[b].rt;while(tp<=tot){int x=s[tp++];if(t[x].ch[0])s[++tot]=t[x].ch[0];if(t[x].ch[1])s[++tot]=t[x].ch[1];T[a].ins_node(x);}}
}D;
signed main(){IOS;cin>>n>>m;D.init();for(int i=1,x;i<=n;i++){cin>>x;T[i].insert(x,i);}while(m--){int x,y;cin>>x>>y;D.mg(x,y);}cin>>q;while(q--){char op;int x,y;cin>>op>>x>>y;if(op=='B')D.mg(x,y);else cout<<T[D.fd(x)].kth(y)<<'\n';}
}