Little Z has a forest containing $N$ nodes, and each node has a non-negative integer as its weight. Initially, there are $M$ edges in the forest.

Little Z wants to perform $T$ operations of two types:

1. Q x y k: Query the $k$-th smallest weight among all weights on the path between node $x$ and node $y$. This operation guarantees that node $x$ and node $y$ are connected, and there are at least $k$ nodes on the path between these two nodes.
2. L x y: Add an edge between node $x$ and node $y$. It is guaranteed that the graph remains a forest after this operation.

To ensure the online nature of the program, the input data is encrypted. Let lastans be the result of the program's last output, with lastans initially being 0.

For an input operation Q x y k, the actual operation is Q x^lastans y^lastans k^lastans. For an input operation L x y, the actual operation is L x^lastans y^lastans.

The ^ operator denotes the XOR operation.

Please write a program to help Little Z complete these operations.

Input

The first line contains a positive integer testcase, representing the test case number. It is guaranteed that $1 \le \text{testcase} \le 20$. The second line contains three integers $N$, $M$, and $T$, representing the number of nodes, the number of initial edges, and the number of operations, respectively. The third line contains $N$ non-negative integers representing the weights on the $N$ nodes. The next $M$ lines each contain two integers $x$ and $y$, representing an undirected edge between node $x$ and node $y$ initially. The next $T$ lines each describe an operation in the format "Q x y k" or "L x y", the meanings of which are described in the problem description.

Output

For each operation of the first type, output a non-negative integer representing the answer.

Examples

Input 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

Output 1

2
2
1
4
2

Note

The decrypted operations are: Q 8 7 3 Q 1 7 3 Q 8 2 2 L 4 5 L 2 3 L 1 6 Q 8 3 4 Q 2 5 2

For the first operation Q 8 7 3, lastans=0, so the actual operation is Q 8^0 7^0 3^0, which is Q 8 7 3. There are 5 nodes on the path from node 8 to node 7, and their weights are 4, 1, 1, 2, 4. Among these weights, the 3rd smallest is 2. Output 2, and lastans becomes 2.

For the second operation Q 3 5 1, lastans=2, so the actual operation is Q 3^2 5^2 1^2, which is Q 1 7 3. There are 4 nodes on the path from node 1 to node 7, and their weights are 1, 1, 2, 4. Among these weights, the 3rd smallest is 2. Output 2, and lastans becomes 2.

Subsequent operations are similar.

Constraints

Note: N/A means no special properties.

For 100% of the test data: all node indices are in the range $1..N$. Weights on nodes are $\le 10^9$. $M < N$.