Để chuẩn bị cho đêm Halloween, Bessie muốn tạo một cây bí ngô để trang trí cho căn nhà của mình. Thay vì trang trí cây bí ngô một cách truyền thống, Bessie quyết định xây dựng một cây bí ngô độc đáo và đầy ma mị. Cây bí ngô của Bessie là một cây với ~N~ quả bí ngô được đánh số từ ~1~ ~(1 ≤ N ≤ 2 \times 10^5)~ nối với nhau bằng ~N - 1~ cành. Mỗi quả bí ngô ban đầu chưa được trang trí và Bessie có thể gắn thêm phụ kiện cho các quả bí ngô, các phụ kiện được đánh số từ ~1, 2, ...~ (không quá ~2 \times 10^5)~. Độ ma mị của quả bí ngô bằng số phụ kiện khác nhau mà nó được trang trí.

Biết rằng cây của Bessie có gốc ban đầu là bí ngô số ~1~, có ~2~ tình huống xảy ra:

• Bessie chọn ra một bí ngô ~x~ và trang trí phụ kiện ~c~ cho tất cả các bí ngô thuộc cây bí ngô gốc ~x~ (tính cả bí ngô ~x~).

• Bessie muốn biết cây bí ngô gốc ~x~ có tổng độ ma mị là bao nhiêu. Biết rằng tổng độ ma mị của cây bí ngô gốc ~x~ bằng tổng độ ma mị của từng bí ngô có trong cây bí ngô gốc ~x~ (tính cả bí ngô ~x~).

Nhiệm vụ của bạn là trả lời chính xác các câu hỏi mà Bessie đưa ra.

Dữ liệu vào

• Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~Q\,(Q ≤ 2 \times 10^5) ~.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a, b~ mô tả cạnh nối bí ngô ~a~ với bí ngô ~b~.
• ~Q~ dòng cuối cùng chứa các truy vấn, có ~2~ loại truy vấn:
  • ~1~ ~x~ ~c:~ Bessie sẽ chọn cây bí ngô gốc ~x~ để trang trí phụ kiện ~c\,(1 \le c \le 2\times 10^5)~ lên.
  • ~2~ ~x:~ Bessie cần biết tổng độ ma mị của cây bí ngô gốc ~x~.

Kết quả ra

Với mỗi truy vấn loại ~2~, in ra kết quả ứng với từng bí ngô ~x~.

Ràng buộc

• Subtask ~1 (30\%):~ ~N \le 200, Q \le 200~.
• Subtask ~2 (20\%):~ ~N \le 3000, Q \le 3000~.
• Subtask ~3 (30\%):~ cây có dạng đoạn thẳng, ~N \le 2 \times 10^5, Q \le 2 \times 10^5~.
• Subtask ~4 (20\%):~ không có ràng buộc gì thêm.

Ví dụ

Dữ liệu

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

Kết quả

1
0
2
2
5
3

Giải thích

• Truy vấn ~1~: cây bí ngô gốc ~4~ được trang trí phụ kiện ~1~, độ ma mị bí ngô ~4~ tăng ~1~.
• Truy vấn ~2~: cây bí ngô gốc ~1~ có ~5~ bí ngô ~1, 2, 3, 4, 5~ có độ ma mị lần lượt là ~0, 0, 0, 1, 0~ và tổng độ ma mị của cây là ~1~.
• Truy vấn ~3~: cây bí ngô gốc ~2~ có ~1~ bí ngô ~2~ có độ ma mị là ~0~.
• Truy vấn ~4~: cây bí ngô gốc ~5~ được trang trí phụ kiện ~1~, độ ma mị bí ngô ~5~ tăng ~1~.
• Truy vấn ~5~: cây bí ngô gốc ~1~ có ~5~ bí ngô ~1, 2, 3, 4, 5~ có độ ma mị lần lượt là ~0, 0, 0, 1, 1~ và tổng độ ma mị của cây là ~2~.
• Truy vấn ~6~: cây bí ngô gốc ~3~ có ~3~ bí ngô ~3, 4, 5~ có độ ma mị lần lượt là ~0, 1, 1~ và tổng độ ma mị là ~2~.
• Truy vấn ~7~: cây bí ngô gốc ~1~ được trang trí phụ kiện ~1~, các bí ngô ~1, 2, 3, 4, 5~ thuộc cây bí ngô gốc ~1~ nên được trang trí phụ kiện ~1~. Độ ma mị bí ngô ~1, 2, 3~ tăng ~1~, riêng bí ngô ~4, 5~ đã được trang trí phụ kiện ~1~ nên độ ma mị không tăng.
• Truy vấn ~8~: cây bí ngô gốc ~1~ có tổng độ ma mị là ~5~.
• Truy vấn ~9~: cây bí ngô gốc ~3~ có tổng độ ma mị là ~3~.