Description

Note: In this problem, every $\sum$ means taking the XOR-sum.

There is a rooted tree with $n$ nodes and $n-1$ edges. Initially, node $1$ is the root.

Each node $i$ on the tree has a node value $V_{i}$.

Define the function $\operatorname{Xor}(x)=\sum_{y\in \operatorname{Subtree}(x)}{V_{y}}$, where $\operatorname{Subtree}(x)$ denotes the subtree of $x$.

You need to support the following five operations:

1. 1 x: Make $x$ the root, and query $\sum_{i=1}^{n}{\operatorname{Xor}(i)}$.
2. 2 x y: Set $V_{x}=y$.
3. 3 x y: Query $\operatorname{LCA}(x,y)$.
4. 4 x y: Query the XOR-sum of node values along the path from $x$ to $y$.
5. 5 x: Query $\operatorname{Xor}(x)$.

Input Format

The first line contains three integers $n,m,q$, representing the number of nodes, the number of operation type $1$, and the number of the remaining operations.

The next line contains $n$ integers, representing $V_{1}\dots V_{n}$.

The next $n-1$ lines each contain two integers $x,y$, indicating that there is an edge between $x$ and $y$.

The next $m+q$ lines each contain two or three integers. The first number is the operation type, followed by the parameters of that operation.

Output Format

Output several lines, each being the result of operations $1,3,4,5$.

5 4 4
0 0 2 2 1
1 2
1 3
2 4
2 5
1 1
1 1
1 1
2 3 0
4 3 3
5 1
1 2
3 1 2

3
3
3
0
3
0
2

10 8 8
5 6 2 1 0 4 0 0 0 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
3 10 9
2 1 6
1 5
1 4
1 7
1 7
5 1
1 1
3 1 5
1 7
1 9
2 5 0
4 9 6
1 10
4 10 7
5 1

2
3
3
3
3
2
3
1
3
7
7
7
1
0

Hint

For all testdata, it is guaranteed that $100\le n,m,q\le 10^6$, $0\le V_i\le 2^{31}-1$. The detailed Constraints are shown in the table below.

Translated by ChatGPT 5