Description

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

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

• Q x y k Query the $k$-th smallest weight among all the weights on the path from $x$ to $y$. It is guaranteed that $x$ and $y$ are connected, and there are at least $k$ nodes on this path.
• L x y Add an edge between nodes $x$ and $y$. It is guaranteed that after this operation, the graph is still a forest.

To make the program online, the input is encrypted. Let $lastans$ be the last printed answer, initially $0$.

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

For an input operation L x y, the real operation is L x^lastans y^lastans. Here the operator ^ denotes bitwise XOR, equivalent to xor in Pascal.

Please write a program to help Xiao Z finish these operations.

Input Format

The first line contains a positive integer $\mathrm{testcase}$, indicating the test point index of the current testdata.

The second line contains three integers $N, M, T$, denoting 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 of the $N$ nodes.

The next $M$ lines each contain two integers $x$ and $y$, indicating that initially there is an undirected edge between $x$ and $y$.

The next $T$ lines each describe an operation, in the format Q x y k or L x y, as defined above.

Output Format

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

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

Hint

Sample explanation:

For the first operation Q 8 7 3, at this time $lastans = 0$, so the real operation is Q 8^0 7^0 3^0, i.e., Q 8 7 3. There are $5$ nodes on the path from $8$ to $7$, and their weights are $4, 1, 1, 2, 4$. Among these weights, the $3$-rd smallest is $2$, so output $2$, and $lastans$ becomes $2$.

For the second operation Q 3 5 1, at this time $lastans = 2$, so the real operation is Q 3^2 5^2 1^2, i.e., Q 1 7 3. There are $4$ nodes on the path from $1$ to $7$, and their weights are $1, 1, 2, 4$. Among these weights, the $3$-rd smallest is $2$, so output $2$, and $lastans$ becomes $2$. The subsequent operations are similar.

Constraints

Note: N/A means no special property.

For $100\%$ of the testdata, all node indices are in the range $1 \sim N$. Each node’s weight $\le 10^9$. $M < N$.

Translated by ChatGPT 5