[SDOI2013]森林

题目描述

小Z有一片森林,含有N个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有M条边。 小Z希望执行T个操作,操作有两类: 1. `Q x y k`查询点x到点y路径上所有的权值中,第k小的权值是多少。此操作保证点x和点y连通,同时这两个节点的路径上至少有k个点。 2. `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完成这些操作。 对于所有的数据,n,m,T<=$8*10^4$.

输入输出格式

输入格式


第一行包含一个正整数testcase,表示当前测试数据的测试点编号。保证1<=testcase<=20。 第二行包含三个整数N,M,T,分别表示节点数、初始边数、操作数。 第三行包含N个非负整数表示 N个节点上的权值。 接下来 M行,每行包含两个整数x和 y,表示初始的时候,点x和点y 之间有一条无向边。 接下来 T行,每行描述一个操作,格式为”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,此时 lastans=0,所以真实操作为Q 8^0 7^0 3^0,也即Q 8 7 3。点8到点7的路径上一共有5个点,其权值为4 1 1 2 4。 这些权值中,第三小的为 2,输出 2,lastans变为2。 对于第二个操作 Q 3 5 1 ,此时lastans=2,所以真实操作为Q 3^2 5^2 1^2 ,也即Q 1 7 3。点1到点7的路径上一共有4个点,其权值为 1 1 2 4 。 这些权值中,第三小的为2,输出2,lastans变为 2。之后的操作类似。 ![](https://cdn.luogu.org/upload/pic/17889.png)