Bạn được cho một cây gồm ~n~ đỉnh, trong đó mỗi đỉnh chứa một giá trị ban đầu. Nhiệm vụ của bạn là thực hiện hai loại thao tác chính:

• Cập nhật giá trị: Thay đổi giá trị của một đỉnh cho trước.
• Tính tổng cây con: Tính tổng các giá trị của tất cả các đỉnh nằm trong cây con có gốc tại một đỉnh xác định.

Dữ liệu vào

• Dòng đầu chứa số nguyên ~n~ là số đỉnh của cây.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ là giá trị ban đầu của từng đỉnh.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ biểu diễn một cạnh giữa hai đỉnh ~u~ và ~v~.
• Dòng tiếp theo chứa một số nguyên ~q~ là số lượng truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:
  • ~1~ ~x~ ~v~: Cập nhật giá trị của đỉnh ~x~ thành ~v~.
  • ~2~ ~x~: Tính tổng giá trị của các đỉnh trong cây con gốc tại ~x~.

Dữ liệu ra

• Với mỗi truy vấn dạng ~2~ ~x~, in ra một số nguyên là tổng giá trị các đỉnh trong cây con gốc tại ~x~.

Input

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

Output

8
10

Ràng buộc

• ~1 \leq n, q \leq 200000~
• ~-10^9 \leq a_i \leq 10^9~
• ~1 \leq u, v, x \leq n~

Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1, 2, \dots, 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 giá trị trên đường đi từ gốc cây tới nút ~s~

Dữ liệu vào

• Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~q~ là số lượng nút và truy vấn. Các nút được đánh số ~1, 2, \dots, n~.
• Dòng tiếp theo có ~n~ số nguyên ~v_1, v_2, \dots, v_n~ là 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~".

Dữ liệu ra

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

Input

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

Output

11
8

Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số từ ~1~ đến ~n~ và nút ~1~ là gốc của cây. Mỗi nút có một màu. Nhiệm vụ của bạn là với mỗi nút, xác định số lượng màu phân biệt trong cây con của nó.

Dữ liệu vào

• Dòng đầu vào đầu tiên chứa một số nguyên ~n (1 \le n \le 2 \times 10^5)~ là số lượn nút. Các nút được đánh số từ 1~ đến ~n~.
• Dòng tiếp theo bao gồm ~n~ số nguyên ~c_1, c_2, \dots, c_n (1 \le c_i \le 10^9)~ là màu sắc 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 (1 \le a, b \le n)~ là có một cạnh nối hai nút ~a~ và ~b~.

Dữ liệu ra

• ~n~ số nguyên: với mỗi nút ~1, 2, \dots, n~ in ra số lượng màu khác nhau.

Input

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

Output

3 1 2 1 1