[SDOI2013]森林
题号：NC20577
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小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

输出

复制 
2
2
1
4
2

备注: