Background

This is a template problem, with no $rap$.

Problem Description

On a piece of land, there are $n$ cities. They are connected by $n-1$ undirected edges, forming a tree. The distance between two adjacent cities is $1$. The value of city $i$ is $value_i$.

Unfortunately, earthquakes often happen on this land, and as time goes on, the values of cities may also change.

You need to process $m$ operations online:

0 x k means an earthquake happens, with the epicenter at city $x$ and an affected radius of $k$. All cities whose distance to $x$ is at most $k$ will be affected. The economic loss of this earthquake is the sum of the values of all affected cities.

1 x y means the value of city $x$ becomes $y$.

To ensure the online nature of the program, in each operation, $x$, $y$, and $k$ must be decrypted by XOR with the output of your previous query. If there has been no output before, the previous output is considered to be $0$ by default.

Input Format

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ positive integers. The $i$-th number denotes $value_i$.

The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating an undirected edge between $u$ and $v$.

The next $m$ lines each contain three numbers, describing the $m$ operations.

Output Format

Output several lines. For each query, output one positive integer per line as the answer.

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

11100101

Hint

Constraints

For $100\%$ of the testdata, $1\leq n,m\leq 10^5$, $1\leq u,v,x\leq n$, $1\leq value_i,y\leq 10^4$, $0\leq k\leq n-1$.

upd: The sample constraints are different from the real constraints. Please use the constraints given in the hint.

Notes

Source: BZOJ3730.

Translated by ChatGPT 5