Problem Description

Country U has $n$ buildings. The first building is the shelter, and they are connected by $n-1$ roads. Each building has a certain number of refugees. Initially, the number of refugees in building $i$ is $a_i$.

During the war, $q$ events occur. There are two types of events:

• 1 x y: The number of refugees in building $x$ becomes $y$.

• 2 x: The road that is closest to the shelter on the path from building $x$ to the shelter changes its state: if it was open, it becomes blocked; otherwise, it becomes open. At the beginning, every road is open. It is guaranteed that $x \neq 1$.

After each event, you need to output how many refugees can reach the shelter by following open roads.

Input Format

The first line contains two positive integers $n, q$.

The next $n-1$ lines each contain two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

The next line contains $n$ integers $a_i$.

The following $q$ lines each contain two or three integers, representing one event.

Output Format

Output $q$ lines. Each line contains one number, representing the answer.

4 6
1 2
2 3
3 4
1 1 1 1
1 2 2
2 4
2 2
1 4 10
2 4
2 2

5
4
1
1
1
14

9 15
1 2
1 3
3 4
3 5
4 6
3 7
7 8
7 9
5 65 70 8 1 500 18 21 180
2 7
1 3 200
2 3
1 6 300
2 6
1 9 100
2 7
2 6
1 4 20
2 2
2 3
1 2 9
1 7 0
2 3
2 2

649
779
70
70
70
70
70
70
70
5
665
665
647
5
14

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq n, q \leq 10^5$ and $0 \leq a_i, y \leq 10^9$.

Notes

Translated from AGM 2022 Qualification Round J Shelters。

Translated by ChatGPT 5