P3302 [SDOI2013] Forest

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.

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.

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

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 | Test point index | Upper bounds of $N, M, T$ | `L` operations | `Q` operations | Structure | | :--------------: | :-----------------------: | :------------: | :------------: | :-------: | | $1$ | $20$ | N/A | N/A | N/A | | $2$ | $200$ | N/A | N/A | N/A | | $3\sim 4$ | $4\times 10^4$ | No `L` operations | N/A | Chain | | $5\sim 6$ | $8\times 10^4$ | No `L` operations | N/A | Chain | | $7\sim 9$ | $8\times 10^4$ | No `L` operations | Guaranteed $k=1$ | N/A | | $10\sim 11$ | $4\times 10^4$ | N/A | Guaranteed $k=1$ | N/A | | $12\sim 13$ | $8\times 10^4$ | N/A | Guaranteed $k=1$ | N/A | | $14\sim 15$ | $4\times 10^4$ | No `L` operations | N/A | N/A | | $16\sim 17$ | $8\times 10^4$ | No `L` operations | N/A | N/A | | $18$ | $4\times 10^4$ | N/A | N/A | N/A | | $19\sim 20$ | $8\times 10^4$ | N/A | N/A | N/A | 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