#103123. [BZOJ 3123] [Sdoi2013]森林

小 Z 有一片森林，含有 个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有 条边。小 Z 希望执行 个操作，操作有两类：

• Q x y k 查询点 到点 路径上所有的权值中，第 小的权值是多少。此操作保证点 和点 连通，同时这两个节点的路径上至少有 个点。
• L x y 在点 和点 之间连接一条边。保证完成此操作后，仍然是一片森林。

为了体现程序的在线性，我们把输入数据进行了加密。设 为程序上一次输出的结果，初始的时候 为 。 对于一个输入的操作 Q x y k，其真实操作为 Q x^lastans y^lastans k^lastans。 对于一个输入的操作 L x y，其真实操作为 L x^lastans y^lastans。其中 ^ 运算符表示异或，等价于 Pascal 中的 xor 运算符 请写一个程序来帮助小 Z 完成这些操作。

第一行包含一个正整数 ，表示当前测试数据的测试点编号。第二行包含三个整数 ，分别表示节点数、初始边数、操作数。第三行包含 个非负整数表示 个节点上的权值。接下来 行，每行包含两个整数 和 ，表示初始的时候，点 和点 之间有一条无向边。 接下来 行，每行描述一个操作，格式为 Q x y k 或者 L x y ，其含义见题目描述部分。

对于每一个第一类操作，输出一个非负整数表示答案。

样例输入 #1

1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3
Q 3 5 1
Q 10 0 0
L 5 4
L 3 2
L 0 7
Q 9 2 5
Q 6 1 6

样例输出 #1

2 
2
1
4
2

样例说明

对于第一个操作 Q 8 7 3 ，此时 ，所以真实操作为 Q 8^0 7^0 3^0，也即 Q 8 7 3 。点 到点 的路径上一共有 个点，其权值为 。这些权值中，第三小的为 ，输出 ， 变为 。 对于第二个操作 Q 3 5 1 ，此时 ，所以真实操作为 Q 3^2 5^2 1^2，也即 Q 1 7 3。点 到点 的路径上一共有 个点，其权值为 。这些权值中，第三小的为 ，输出 ， 变为 。之后的操作类似。

对于 的数据，所有节点的编号在 的范围内。节点上的权值 。。