Tổng đường đi

Cho một cây có gốc gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\), và đỉnh \(1\) là gốc của cây. Mỗi đỉnh \(i\) có một giá trị nguyên dương \(v_i\).

Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai loại sau:

• Thay đổi giá trị: Gán giá trị của đỉnh \(s\) thành \(x\).
• Tính tổng đường đi: Tính tổng giá trị của tất cả các đỉnh trên đường đi từ gốc (đỉnh \(1\)) đến đỉnh \(s\) (bao gồm cả hai đầu).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n, q \le 2 \cdot 10^5)\) --- số lượng đỉnh của cây và số lượng truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) \((1 \le v_i \le 10^9)\) --- giá trị ban đầu của các đỉnh.

\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \le a, b \le n)\) --- mô tả một cạnh nối giữa hai đỉnh \(a\) và \(b\). Đảm bảo các cạnh này tạo thành một cây.

\(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Dạng 1 s x \((1 \le s \le n, 1 \le x \le 10^9)\): thay đổi giá trị của đỉnh \(s\) thành \(x\).
• Dạng 2 s \((1 \le s \le n)\): tính tổng giá trị các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(s\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng giá trị cần tìm.

Example

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4

11
8