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