Bạn được cho một cây có gốc gồm \(n\) nút. Các nút được đánh số từ \(1, 2, ..., n\), và nút \(1\) là gốc. Mỗi nút có một giá trị. Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• Thay đổi giá trị của nút \(s\) thành \(x\).
• Tính tổng các giá trị trên đường đi từ gốc đến nút \(s\).

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số lượng nút và số lượng truy vấn. Các nút được đánh số từ \(1\) đến \(n\).
• Dòng tiếp theo gồm \(n\) số nguyên \(v_1, v_2, ..., v_n\): giá trị của mỗi nút.
• Sau đó có \(n - 1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối giữa các nút \(a\) và \(b\).
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi truy vấn có một trong hai dạng sau:
• "1 s x" - thay đổi giá trị của nút \(s\) thành \(x\).
• "2 s" - tính tổng các giá trị trên đường đi từ gốc đến nút \(s\).

Dữ liệu ra:

• In ra câu trả lời cho mỗi truy vấn dạng \(2\)

Ràng buộc

• \(1 \le n,q \le 2 \times 10^5\)
• \(1 \le a,b,s \le n\)
• \(1 \le v_i,x \le 10^9\)

Input 1

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

Output 1

11
8