Tổng Trên Đường Từ Gốc

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:

• $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 các đỉnh trên đường đi duy nhất từ gốc $1$ đến $s$, kể cả hai đầu mút.

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 trên đường từ gốc đến đỉnh được hỏi.

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$ ($30\%$ số điểm): $n,q\le 1000$.
• Subtask $2$ ($70\%$ 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 5
1 2 6
2 4
2 6
1 1 1
2 6

13
13
12
8