1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
char getop() {
    char c;
    while (true) {
    	c = getchar();
    	if (c == 'Q') return 'Q';
		if (c == 'B') return 'B';
	}
}
const int maxn = 100005;
const int maxm = 300005;
int siz[maxn], root[maxn], F[maxn], val[maxn], c[maxn][2], fa[maxn];
void pu(int x) {
	siz[x] = 1;
	if (c[x][0]) siz[x] += siz[c[x][0]];
	if (c[x][1]) siz[x] += siz[c[x][1]];
}
void rotate(int x) {
	int y = fa[x], z = fa[y], a = c[y][1]==x, b = a ^ 1;
	if (z) c[z][c[z][1]==y] = x;
	fa[x] = z; fa[y] = x; fa[c[x][b]] = y;
	c[y][a] = c[x][b]; c[x][b] = y;
	fa[0] = 0; pu(y); pu(x);
}
int splay(int x) {
	while (fa[x]) {
		int y = fa[x], z = fa[y];
		if (z) {
			if (c[y][0] == x ^ c[z][0] == y) rotate(x);
			rotate(y);
		}
		rotate(x);
	}
	return x;
}
int insert(int &x, int y, int father) {
	if (!x) {
		x = y;
		fa[y] = father;
		return splay(y);
	}
	if (val[y] < val[x]) return insert(c[x][0], y, x);
	return insert(c[x][1], y, x);
}
void dfs_merge(int x, int y) {
	if (c[x][0]) { dfs_merge(c[x][0], y); c[x][0] = 0; }
	if (c[x][1]) { dfs_merge(c[x][1], y); c[x][1] = 0; }
	root[y] = insert(root[y], x, 0);
}
int find(int x) {
	return x == F[x] ? x : F[x] = find(F[x]);
}
int n, m;
int query(int x, int k) {
	int l = c[x][0], ls = siz[l];
	if (k == ls + 1) return x;
	if (k <= ls) return query(l, k);
	return query(c[x][1], k - ls - 1);
}
int main() {
	n = getint(); m = getint();
	int a, b;
	for (int i = 1; i <= n; ++i) {
		val[i] = getint();
		root[i] = i;
		F[i] = i;
		siz[i] = 1;
	}
	for (int i = 1; i <= m; ++i) {
		a = find(getint()); b = find(getint());
		if (siz[root[a]] < siz[root[b]]) swap(a, b);
		dfs_merge(root[b], a);
		F[b] = a;
	}
	int T = getint(), x, y;
	while (T--) {
		if (getop() == 'Q') {
			x = getint(); y = getint(); a = root[find(x)];
			if (siz[a] < y) puts("-1");
			else printf("%d\n", query(root[a], y));
		} else {
			a = find(getint()); b = find(getint());
			if (siz[root[a]] < siz[root[b]]) swap(a, b);
			dfs_merge(root[b], a);
			F[b] = a;
		}
	}
    return 0;
}