Tổng Trong Cây Con

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$, được chọn gốc tại đỉnh $1$. Mỗi đỉnh $i$ có giá trị hiện tại $a_i$.

Bạn cần xử lý $q$ thao tác trực tuyến thuộc một trong hai loại:

• $1$ $s$ $x$: thay giá trị của đỉnh $s$ bằng $x$;
• $2$ $s$: tính tổng giá trị hiện tại của tất cả các đỉnh thuộc cây con gốc $s$, trong đó có cả đỉnh $s$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $u,v$, biểu diễn một cạnh vô hướng của cây.

• Mỗi dòng trong $q$ dòng cuối mô tả một thao tác theo một trong hai dạng trên.

Output

• Với mỗi thao tác loại $2$, in tổng cần tìm trên một dòng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le a_i\le 10^9$.
• Với thao tác $1$ $s$ $x$: $1\le s\le n,1\le x\le 10^9$.
• Với thao tác $2$ $s$: $1\le s\le n$.
• Các cạnh tạo thành một cây có gốc tại $1$.
• Kết quả có thể vượt phạm vi số nguyên $32$ bit có dấu.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 5000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6 6
5 1 4 2 7 3
1 2
1 3
2 4
2 5
3 6
2 2
1 5 10
2 1
2 3
1 1 8
2 1

10
25
7
28