Dynamic Tree Queries with XOR Sum

This problem involves processing dynamic queries on a rooted tree. Initially, you are given a tree with \(n\) nodes and \(n-1\) edges, with node 1 as the root. Each node \(i\) has an associated value \(V_{i}\). Note: In this problem, every \(\sum\) denotes the bitwise XOR sum.

Define the function \[ \operatorname{Xor}(x)=\bigoplus_{y\in \operatorname{Subtree}(x)} V_{y}, \] where \(\operatorname{Subtree}(x)\) is the subtree rooted at node \(x\).

You need to support the following five types of operations:

1. 1 x: Change the tree root to node \(x\), and then query \( \bigoplus_{i=1}^{n} \operatorname{Xor}(i)\).
2. 2 x y: Update the value of node \(x\) to \(y\), i.e. set \(V_{x}=y\).
3. 3 x y: Query the Lowest Common Ancestor (LCA) of nodes \(x\) and \(y\).
4. 4 x y: Query the XOR sum of the node values on the path from \(x\) to \(y\).
5. 5 x: Query \(\operatorname{Xor}(x)\), i.e. the XOR sum of the values in the subtree of \(x\).

All queries of type 1, 3, 4, and 5 require an output. The tree is dynamic in the sense that the root may change; the subtree and LCA computations are to be made with respect to the current root.

inputFormat

The first line contains two integers \(n\) and \(Q\), representing the number of nodes and the number of operations.

The second line contains \(n\) integers \(V_{1}, V_{2}, \dots, V_{n}\) — the initial values of the nodes.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating there is an edge between nodes \(u\) and \(v\) (the tree is undirected).

Each of the next \(Q\) lines contains one query in one of the following formats:

• 1 x
• 2 x y
• 3 x y
• 4 x y
• 5 x

outputFormat

For each query of type 1, 3, 4, or 5, output the corresponding result on a separate line in the order of the queries.

sample

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

0
0
1
2