Subtree XOR Queries on a Rooted Tree

You are given a rooted tree with \( n \) nodes, where the root is node \( 1 \) and the weight of node \( i \) is \( a_i \) for \( i \in [1, n] \). The tree is provided by its \( n-1 \) edges.

You need to process \( m \) operations of the following two types:

• \( 1\ x\ y \): Update the weight of node \( x \) to \( y \).
• \( 2\ x \): Query the XOR sum of the weights of all nodes in the subtree with root \( x \).

For each query (operation of type 2), output the correct result.

Note: The XOR operator is denoted by \( \oplus \) in mathematical notation.

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of nodes in the tree and the number of operations).

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \), representing the initial weights of the nodes.

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \), indicating an edge between nodes \( u \) and \( v \). The tree is rooted at node \( 1 \).

The following \( m \) lines each describe an operation. An operation is in one of the following formats:

• 1 x y: Update the weight of node \( x \) to \( y \).
• 2 x: Query the XOR sum of the weights of all nodes in the subtree rooted at \( x \).

outputFormat

For each query (operation of type 2), output a single line containing the XOR sum of the weights in the specified subtree.

sample

5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
2 1
1 3 10
2 3
1 2 7
2 2

1
10
6