永无乡solution

(尚未讲解)
前置技能：并查集及其“代表”思想；权值线段树（会讲解）；权值线段树上二分求k-th（会讲解）；动态开点（会讲解）;线段树合并(会讲解)

PS1：此题是有平衡树的解法的，但其实麻烦了（其实是我不太会）
PS2：如果你不会并查集，那你有必要先去学一下

先关注“联通”二字，即要维护图上的联通性。而并查集非常适合解决此类问题。
由此，我们得到一个暴力做法：
对于合并操作，直接在并查集上合并x,y即可，每次$O(1)$；
对于查询操作，直接找出所有与x同一集合的点，按重要度排序后第k小即为所求，最坏每次$O(nlogn)$;
总时间复杂度最坏$O(q\times nlogn)$。

看到查询居然要最坏每次$O(nlogn)$的复杂度，有很大的优化空间。
如何动态求k-th?
如果您想到了平衡树,那么您就已经可以解决此题了,不用继续往下了.
而如果您不是很会平衡树:
权值线段树也能(通过线段树上二分)$O(logn)$动态维护k-th可以参见这里
也就是说,我们要查询与x联通的点里面第k重要的,就可以这样实现$O(logn)$的查询
但这样有两个问题:
1. 空间开销大.对于每个点都开一个大小为$O(n)$的线段树,总空间复杂度$O(n^2)$,无法承受.考虑到每次询问实际用到的点仅$O(logn)$个,总共也就最多访问$O(qlogn)$个节点,使用动态开点 (没错,还是同一篇blog),将空间降为$O(min(n^2,qlogn))$
2. 每次合并x,y时,要将与其联通的所有点都插入它们,每次最坏甚至可能超越$O(n)$.考虑并查集的”代表”思想:设sgt(i)表示与点i联通的点构成的线段树,由于联通是双向的,有:$$sgt(x)=sgt(y)\ if(x,y联通)$$也就是说,在并查集上合并(x,y)的同时,把sgt(x)也与sgt(y)合并,查询时在find(x)上查询.
这带来了新的问题:普通的合并,复杂度不会低于$O(n)$.可以使用启发式合并,这样大概是两个log.但更优的做法是使用线段树合并
权值线段树的线段树合并代码大概是这样的:

typedef long long ll;
typedef unsigned un;
ll uni(ll a,ll b,un l=1,un r=n)//把sgt(a)合并到sgt(b)上,并返回合并后点的编号
{
    if(!a)return b;//有一个为空,返回
    if(!b)return a;
    if(l==r)//叶子节点,直接合并
    {
        t[b].v+=t[a].v;
        return b;
    }
    un mid=(l+r)>>1;
    t[b].ls=uni(t[a].ls,t[b].ls,l,mid);//递归合并子节点
    t[b].rs=uni(t[a].rs,t[b].rs,mid+1,r);
    pushup(b);//更新当前点
    return b;
}

每个点至多被合并一次,总复杂度$O((m+q)logn)$

再讲解一下几个细节:初始化并查集;每个点先把自己的重要度插入自己的线段树里;合并的时候都是对find(x),find(y)进行合并;
最后,总时间复杂度$O((n+m+q)logn)$,空间复杂度$O(min(n^2,qlogn))$

//Wan Hong 3.0
//notebook
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <cmath>
typedef int ll;//long long makes MLE.
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
    ll f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}
ll min(ll a,ll b)
{
    return a<b?a:b;
}
bool umax(ll& a,ll b)
{
    if(b>a)return a=b,1;
    return 0;
}
bool umin(ll& a,ll b)
{
    if(b<a)return a=b,1;
    return 0;
}

/**********/
#define MAXN 300011
struct ufs//Union_Find_Set
{
    ll fa[MAXN];
    void build(ll n)
    {
        for(ll i=1;i<=n;++i)fa[i]=i;
    }
    ll find(ll x)
    {
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
    void uni(ll u,ll v)
    {
        u=find(u),v=find(v);
        fa[u]=v;
    }
}s;
ll n,m,q;

struct node//线段树的节点(动态开点的)
{
    ll v,ls,rs;
    node()
    {
        v=ls=rs=0;
    }
    node(ll _v,ll _ls,ll _rs)
    {
        v=_v,ls=_ls,rs=_rs;
    }
}t[MAXN*18+1];
ll cnt=0;

void pushup(un num)
{
    t[num].v=t[t[num].ls].v+t[t[num].rs].v;
}
void modify(ll x,ll k,un num,un l=1,un r=n)在sgt(num)上将x的出现次数加上k
{
    if(l==r)
    {
        if(l==x)t[num].v+=k;
        return;
    }
    un mid=(l+r)>>1;
    if(x<=mid)
    {
        if(!t[num].ls)t[num].ls=++cnt;//动态开点
        modify(x,k,t[num].ls,l,mid);
    }
    else
    {
        if(!t[num].rs)t[num].rs=++cnt;
        modify(x,k,t[num].rs,mid+1,r);
    }
    pushup(num);
}
ll uni(ll a,ll b,un l=1,un r=n)//线段树合并
{
    if(!a)return b;
    if(!b)return a;
    if(l==r)
    {
        t[b].v+=t[a].v;
        return b;
    }
    un mid=(l+r)>>1;
    t[b].ls=uni(t[a].ls,t[b].ls,l,mid);
    t[b].rs=uni(t[a].rs,t[b].rs,mid+1,r);
    pushup(b);
    return b;
}
ll Qkth(ll k,un num,un l=1,un r=n)//权值线段树上求k-th
{
    if(l==r)return l;
    un mid=(l+r)>>1;
    if(k<=t[t[num].ls].v)return Qkth(k,t[num].ls,l,mid);
    else return Qkth(k-t[t[num].ls].v,t[num].rs,mid+1,r);
}
ll v[MAXN],num[MAXN];//重要度排名;重要度排名所对应的点的编号
//main内有一些debug语句,忽略即可
int main()
{
    //freopen("out.out","w",stdout);
    n=read(),m=read();
    s.build(n);
    cnt=n;//我这里用了一个技巧,把i表示的线段树的编号就设为i
    for(ll i=1;i<=n;++i)
    {
        v[i]=read();
        num[v[i]]=i;
        modify(v[i],1,i);//插入自己的重要度
    }
    for(ll i=1;i<=m;++i)
    {
        ll a=s.find(read()),b=s.find(read());//合并的是并查集上的根节点
        if(a==b)continue;//同一集合内不用合并
        s.uni(a,b);//并查集上合并
        uni(a,b);//线段树上合并
    }
    q=read();
    for(ll i=1;i<=q;++i)
    {
        char op=getchar();
        while(op!='B'&&op!='Q')op=getchar();
        //printf("task %d:",i);
        if(op=='B')
        {
            ll a=s.find(read()),b=s.find(read());
            //printf("a=%d,size=%d;b=%d,size=%d\n",a,t[a].v,b,t[b].v);
            if(a==b)continue;//同一集合内不用合并
            s.uni(a,b);//并查集上合并
            uni(a,b);//线段树上合并
            //printf("unisize=%d\n",t[b].v);
        }
        else
        {
            ll a=s.find(read()),k=read();//权值线段树上求k-th
            //printf("Query %d,size=%d\n",a,t[a].v);
            if(k>t[a].v)printf("-1\n");
            else printf("%d\n",num[Qkth(k,a)]);
        }
        //printf("pass %lld...\n",i);
    }
    return 0;
}