Dynamic Forest Path Kth Query

Given a forest with \(N\) nodes, each node having a non-negative weight, and \(M\) initial edges, process \(T\) operations. There are two types of operations:

• Q x y k: Query the \(k\)-th smallest weight among all nodes on the unique path from node \(x\) to node \(y\). It is guaranteed that \(x\) and \(y\) are connected, and the path contains at least \(k\) nodes.
• L x y: Connect node \(x\) and node \(y\) with an edge. It is guaranteed that after this operation, the graph still forms a forest.

To enforce online processing, the input data are encrypted. Let \(lastans\) be the answer of the previous query, initially \(lastans = 0\). For an input operation:

• For Q x y k, the actual operation is Q (x \oplus lastans) (y \oplus lastans) (k \oplus lastans).
• For L x y, the actual operation is L (x \oplus lastans) (y \oplus lastans).

Here, \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The first line contains three integers \(N\), \(M\), and \(T\). The second line contains \(N\) non-negative integers representing the weights of the nodes. The following \(M\) lines each contain two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\). The next \(T\) lines each contain an operation in one of the following formats:

• Q x y k
• L x y

Note that the parameters provided in the operations are encrypted as described above.

outputFormat

For each query operation, output a single line containing the answer.

sample

5 2 4
1 5 2 4 3
1 2
2 3
L 3 4
L 4 5
Q 1 5 3
Q 1 7 1

3
4