""""
C: Sau này gặp lại tớ nhất định sẽ tặng cho cậu một bó hoa tulip
Q: Sao lại là hoa tulip?
C: Vì nó tượng trưng cho tình yêu vĩnh cữu.
""""

Bạn có biết không, hoa tulip là một loài hoa đặc biệt với đa dạng màu sắc. Với sự kết hợp của nhiều sắc tố trong cánh hoa, màu sắc của chúng có thể biến đổi dựa trên nhiệt độ và ánh sáng mặt trời. Bên cạnh đó, hoa tulip còn có một hệ thống di truyền phức tạp. Ví dụ như việc lai hoa đỏ với hoa xanh có thể tạo ra hoa màu tím. Số lượng cánh hoa của hoa cha và hoa mẹ cũng có thể ảnh hưởng đến số cánh hoa của hoa con. Ví dụ, nếu hoa mẹ có ~5~ cánh và hoa cha có ~3~ cánh, thì hoa con có thể có ~8~ cánh. Điều này được gọi là "học thuyết Aquarius" :>

Biết được điều này nên Q đã đem một sơ đồ gia phả hoa tulip ra đố C. Thay vì đố về màu sắc, Q quyết định đố C về số lượng cánh hoa của các hoa con (vì biết rằng cậu ấy rất hay rối rem với màu sắc ":3" ). Q cho C tất cả ~N~ bông hoa và được đánh số từ ~1~ tới ~N~ với hoa số ~1~ là cội nguồn của tất cả bông hoa khác. Và một mảng số nguyên ~a~ với ~a_i~ tương ứng là số cánh hoa của bông hoa tulip thứ ~i~. Nhiệm vụ của bạn là trả lời ~t~ câu hỏi của Q với một trong hai kiểu sau:

• Thay đổi số cánh hoa hiện tại của hoa tulip thứ ~x~ thành ~y~.
• Tổng số cánh hoa của các hoa con tạo ra từ hoa tulip thứ ~x~ là bao nhiêu?

Ta được biết rằng sơ đồ gia phả của hoa tulip trên có thể được hiểu theo đồ thị cây có gốc trong lý thuyết đồ thị. Để dễ hiểu hơn, bạn có thể tham khảo link sau: https://en.wikipedia.org/wiki/Tree(graphtheory).

Input:

• Dòng đầu tiên gồm một số nguyên ~N~ và ~Q~ là số lượng bông hoa cùng với số câu hỏi, với ~1 \le N, Q \le 2 \cdot 10^5~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ là số lượng cánh hoa của bông hoa thứ ~i~, trong đó ~1 \le a_i \le 10^9.~

• Tiếp theo là ~N-1~ dòng, mỗi dòng chứa ~2~ số nguyên ~a~ và ~b~ cho biết có cạnh nối giữa hoa ~a~ và ~b.~

• Cuối cùng, có ~Q~ dòng mô tả các câu hỏi của Q ở một trong hai dạng:

• Câu hỏi loại 1 sẽ có dạng: ~1~ ~x~ ~y~ nghĩa là thay đổi số cánh hoa của hoa ~x~ thành ~y~
  
• Câu hỏi loại 2 sẽ có dạng: ~2~ ~x~ trả lời tổng số cánh hoa của các hoa con tạo ra từ hoa tulip thứ ~x.~

Output:

Trả lời tất cả các câu hỏi loại 2 ở từng dòng khác nhau.

Sample Input

7 3
4 2 5 2 3 19 6
1 2
1 3
3 5
3 4
5 6
5 7
2 5
1 5 0
2 5

Sample Output

28
25

Nếu như lần sau gặp được cậu
Hy vọng sẽ là một ngày nắng đẹp