Earthquake and City Value

We are given a tree with ( n ) cities (nodes) connected by ( n-1 ) undirected edges so that any two cities are connected by a unique simple path. The distance between two adjacent cities is (1). Each city ( i ) has an associated value ( value_i ). Due to frequent earthquakes, two kinds of operations occur online:

1. An earthquake operation: (0\ x\ k). In an earthquake with epicenter city ( x ) and influence radius ( k ), every city ( u ) with ( d(x,u) \le k ) is affected. The economic loss is defined as the sum of the values of all affected cities. For this operation, you must output the economic loss.

2. An update operation: (1\ x\ y). Change the value of city ( x ) to ( y ).

In order to enforce online processing, the parameters in each operation are encrypted. Specifically, let ( last ) be the output of the most recent earthquake query (initially, ( last = 0 )). For each operation, the given parameters ( x, k, y ) must be replaced by ( x \oplus last,\ k \oplus last,\ y \oplus last ) respectively (where ( \oplus ) denotes the bitwise XOR).

inputFormat

The input begins with a line containing two integers ( n ) and ( m ), representing the number of cities and the number of operations respectively. The next line contains ( n ) integers ( value_1, value_2, \ldots, value_n ), where ( value_i ) is the initial value of the ( i\text{-th} ) city. Then follow ( n-1 ) lines each containing two integers ( u ) and ( v ) indicating there is an edge connecting cities ( u ) and ( v ). Finally, there are ( m ) lines describing the operations. Each operation is in one of the following forms:

• 0 x k

• 1 x y

Note: In every operation, the parameters are given after being XOR-ed with the result of the last earthquake query (if there is no last output, use (0)).

outputFormat

For each earthquake operation (operation type 0), output a single line containing one integer – the economic loss caused by that earthquake.

sample

5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
0 1 1
1 4 12
0 4 4
1 18 22
0 18 22

6
23
11