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