Cho một cây gồm $n$ đỉnh (cây là đồ thị vô hướng, liên thông và không có chu trình). Các đỉnh này được đánh số từ $1$ đến $n$. Đỉnh $1$ là đỉnh gốc của cây, mỗi đỉnh đều có chứa một giá trị.

Bạn cần thực hiện q truy vấn, có hai loại truy vấn khác nhau:

1. Thay đổi giá trị trên đỉnh $s$ thành $x$;
2. Tính tổng giá trị của các đỉnh trên đường đi từ đỉnh gốc (đỉnh $1$) đến đỉnh $s$.

Input

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $q$: số lượng đỉnh và số lượng truy vấn;
• Dòng tiếp theo chứa $n$ số nguyên dương $v_1, v_2,\ldots v_n$: giá trị của mỗi đỉnh;
• Sau đó là $n-1$ dòng mô tả các cạnh của cây. Mỗi dòng gồm hai số nguyên dương $a$ và $b$: thể hiện có cạnh nối giữa hai đỉnh $a$, $b$;
• Cuối cùng là $q$ dòng thể hiện các truy vấn. Mỗi truy vấn thuộc một trong hai dạng: 1 s x hoặc 2 s.

Output

• In ra câu trả lời cho các truy vấn loại 2, mỗi số in trên một dòng.

Ràng buộc

• $1\leq n, q\leq 2\times 10^5$;
• $1\leq a, b, s\leq n$;
• $1\leq v_i, x\leq10^9$.

Ví dụ

Sample input

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

Sample output

11
8