小 Z 有一片森林，含有 N 个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有 M 条边。

小Z希望执行 T 个操作，操作有两类：

Q x y k 查询点 x 到点 y 路径上所有的权值中，第 k 小的权值是多少。此操作保证点 x 和点 y 连通，同时这两个节点的路径上至少有 k 个点。
L x y 在点 x 和点 y 之间连接一条边。保证完成此操作后，仍然是一片森林。
为了体现程序的在线性，我们把输入数据进行了加密。设 lastans 为程序上一次输出的结果，初始的时候 lastans 为 0。

对于一个输入的操作 Q x y k，其真实操作为 Q x^lastans y^lastans k^lastans。

对于一个输入的操作 L x y，其真实操作为 L x^lastans y^lastans。其中 ^ 运算符表示异或，等价于 Pascal 中的 xor 运算符。

请写一个程序来帮助小 Z 完成这些操作。
思路:
树上节点第k小, 我们很容易想到主席树, 但是操作2却有连边操作, 这时候我们可以考虑按树的秩的大小来合并两棵树, 并重新维护被合并的树上的主席树.
tips: 不同于一段序列上的kth查询, 树上kth查询需要求出两节点的lca, 以及lca的father, 类似于树上点差分.
这题空间得开很大, 因为每次合并两棵树都相当于重构一颗主席树.

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace::std;
#define fi first
#define se second
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l + r) >> 1)
#define zty(x) cout << #x << " = " << x << '\n';
const int MAX_N = 8e4 + 5;
const int MAX_M = 1e6 + 5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;

int test;
int n, m, q, t;
int head[MAX_N], tot;
struct node { int to, next;} G[MAX_M * 2];
int a[MAX_N], b[MAX_N], sum;
int fa[MAX_N][20], siz[MAX_N], dep[MAX_N], root[MAX_N];
inline void add(int u, int v) {
    G[++ tot] = node{v, head[u]};
    head[u] = tot;
}
struct President_Tree {
    int root[MAX_N * 150], tot;
    int cnt[MAX_N * 150], son[MAX_N * 150][2];
    int insert(int pre, int l, int r, int pos) {
        int x = ++ tot;
        cnt[x] = cnt[pre] + 1;
        son[x][0] = son[pre][0];
        son[x][1] = son[pre][1];
        if(l == r) return x;
        if(pos <= mid) son[x][0] = insert(son[pre][0], l, mid, pos);
        else son[x][1] = insert(son[pre][1], mid + 1, r, pos);
        return x;
    }
    int query(int x, int y, int ff, int fff, int l, int r, int k) {
        int lcnt = cnt[son[x][0]] + cnt[son[y][0]] - cnt[son[ff][0]] - cnt[son[fff][0]];
        if(l == r) return b[l];
        if(k <= lcnt) return query(son[x][0], son[y][0], son[ff][0], son[fff][0], l, mid, k);
        else return query(son[x][1], son[y][1], son[ff][1], son[fff][1], mid + 1, r, k - lcnt);
    }
} pt;
bitset< MAX_N > vis;
void dfs(int x, int fat, int boss) {
    vis[x] = true;
    fa[x][0] = fat;
    dep[x] = dep[fat] + 1;
    root[x] = boss;
    ++ siz[boss];
    for(int i = 1; i <= t; ++ i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    pt.root[x] = pt.insert(pt.root[fat], 1, sum, a[x]);
    for(int i = head[x]; i; i = G[i].next) {
        int y = G[i].to;
        if(y != fat) dfs(y, x, boss);
    }
}
int lca(int x, int y) {
    if(dep[x] > dep[y]) swap(x, y);
    for(int i = t; i >= 0; -- i) {
        if(dep[fa[y][i]] >= dep[x]) y = fa[y][i];
    }
    if(x == y) return x;
    for(int i = t; i >= 0; -- i) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i]; y = fa[y][i];
        }
    }
    return fa[x][0];
}
void solve() {
    cin >> test;
    cin >> n >> m >> q;
    t = (int)(log(n) / log(2)) + 1;
    for(int i = 1; i <= n; ++ i) {
        cin >> a[i];
        root[i] = i;
    }
    memcpy(b, a, sizeof(a));
    sort(b + 1, b + n + 1);
    sum = unique(b + 1, b + n + 1) - (b + 1);
    for(int i = 1; i <= n; ++ i) a[i] = lower_bound(b + 1, b + sum + 1, a[i]) - b;
    while(m -- ) {
        int x, y;
        cin >> x >> y;
        add(x, y); add(y, x);
    }
    for(int i = 1; i <= n; ++ i) {
        if(!vis[i]) {
            root[i] = i;
            dfs(i, 0, i);
        }
    }
    int lastans = 0;
    while(q -- ) {
        string op;
        int x, y, k;
        cin >> op >> x >> y;
        x ^= lastans;
        y ^= lastans;
        if(op == "Q") {
            cin >> k;
            k ^= lastans;
            int ff = lca(x, y);
            int ret = pt.query(pt.root[x], pt.root[y], pt.root[ff], pt.root[fa[ff][0]], 1, sum, k);
            lastans = ret;
            cout << ret << '\n';
        } else {
            add(x, y); add(y, x);
            int rtx = root[x], rty = root[y];
            if(siz[rtx] < siz[rty]) {
                swap(x, y);
                swap(rtx, rty);
            }
            dfs(y, x, rtx);
        }
    }
}
signed main() {
//    freopen("SPO.IN", "r", stdin);
//    freopen("SPO.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ZTY = 1;
    //cin >> ZTY;
    while(ZTY -- ) solve();
    return 0;
}