Cho một cây có gốc bao gồm \(n\) nút. Các nút được đánh số \(1,2,... ,n\) và nút \(1\) là gốc của cây. 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:

• \(1.\) thay đổi giá trị của nút \(s\) thành \(x\)
• \(2.\) tính tổng các giá trị trong cây con gốc \(s\)

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(q:\) số lượng nút và truy vấn. Các nút được đánh số \(1,2,... ,n.\)
• Dòng tiếp theo có \(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 hai nút \(a\) và \(b\).
• Cuối cùng, có \(q\) các dòng mô tả các truy vấn. Mỗi truy vấn có dạng "\(1\) \(s\) \(x\)" hoặc "\(2\) \(s\)".

Output

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

Constraints

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

Example

Sample Input

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

Sample Output

8
10