永无乡包含 n 座岛，编号从  到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用  到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含  座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。 

Input

输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛  到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 %的数据 n≤,q≤

对于 %的数据 n≤,m≤n，q≤ 

Output

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-。 

Sample Input

Q

Q

B

B

Q

Q

Q

Sample Output

-

题意

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

int val[maxn];

int nxt[maxn],ed[maxn];

int fa[maxn];

void init(){

    For(i,,N){

        ed[i] = i;

        nxt[i] = -;

        fa[i] = i;

    }

}

int find(int p){

    return p == fa[p]?p:fa[p] = find(fa[p]);

}

void Union(int p,int q){

    int fp = find(p),fq = find(q);

    if(fp == fq) return;

    nxt[ed[fp]] = fq;

    ed[fp] = ed[fq];

    fa[fq] = fp;

}

struct Node{

    int op,x,y;

    Node(int op = ,int x = ,int y = ):op(op),x(x),y(y) {}

}node[];

int Index[maxn],tot;

int T[maxn],lson[maxn * ],rson[maxn * ],c[maxn * ];

int build(int l,int r){

    int root = tot++;

    c[root] = ;

    if(l != r){

        int m = (l + r) >> ;

        lson[root] = build(l,m);

        rson[root] = build(m + ,r);

    }

    return root;

}

int update(int root,int pos,int val){

    int newroot = tot++,tmp = newroot;

    c[newroot] = c[root] + val;

    int l = ,r = N;

    while(l < r){

        int m = (l + r) >> ;

        if(pos <= m){

            lson[newroot] = tot++;

            rson[newroot] = rson[root];

            newroot = lson[newroot];

            root = lson[root];

            r = m;

        }else{

            rson[newroot] = tot++;

            lson[newroot] = lson[root];

            newroot = rson[newroot];

            root = rson[root];

            l = m + ;

        }

        c[newroot] = c[root] + val;

    }

    return tmp;

}

int query(int left_root,int right_root,int k){

    int l = ,r = N;

    while(l < r){

        int m = (l + r) >> ;

        if(c[lson[left_root]] - c[lson[right_root]] >= k){

            r = m;

            left_root = lson[left_root];

            right_root = lson[right_root];

        }else{

            l = m + ;

            k -= c[lson[left_root]] - c[lson[right_root]];

            left_root = rson[left_root];

            right_root = rson[right_root];

        }

    }

    return l;

}

int id[maxn];

PII st[maxn];

int POS[maxn];

int main()

{

    Sca2(N,M);

    For(i,,N){

        Sca(val[i]);

        id[val[i]] = i;

    }

    init();

    For(i,,M){

        Sca2(st[i].fi,st[i].se);

        Union(st[i].fi,st[i].se);

    }

    int K; Sca(K);

    For(i,,K){

        char op[]; scanf("%s",op);

        Sca2(node[i].x,node[i].y);

        if(op[] == 'B'){

            node[i].op = ;

            Union(node[i].x,node[i].y);

        }else{

            node[i].op = ;

        }

    }

    int cnt = ;

    For(i,,N){

        if(i == fa[i]){

            for(int j = i; ~j ; j = nxt[j]){

                Index[++cnt] = j;

                POS[j] = cnt;

            }

        }

    }

    T[N + ] = build(,N);

    for(int i = N; i ; i --){

        T[i] = update(T[i + ],val[Index[i]],);

    }

    init();

    For(i,,M) Union(st[i].fi,st[i].se);

    for(int i = ; i <= K ; i ++){

        if(node[i].op == ){

            Union(node[i].x,node[i].y);

        }else{

            int t = find(node[i].x);

            int l = POS[t];

            int r = POS[ed[t]];

            int k = node[i].y;

            //cout << l << "  " << r << "  " << k << endl;

            if(k > r - l +  || k < ){

                puts("-1");

                continue;

            }

            Pri(id[query(T[l],T[r + ],k)]);

        }

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}