Cho một cây gồm ~n~ đỉnh, gốc tại đỉnh ~1~. Ban đầu, giá trị ghi trên mỗi đỉnh đều bằng ~0~. Có ~q~ truy vấn thuộc hai loại:

1. ~1~ ~u~ ~v~ — tăng giá trị của mỗi đỉnh trong cây con gốc ~u~ thêm một lượng ~v~.
2. ~2~ ~u~ — hỏi giá trị hiện tại của đỉnh ~u~.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~, ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai dạng:
  • ~1~ ~u~ ~v~ — tăng mỗi đỉnh trong cây con gốc ~u~ thêm ~v~;
  • ~2~ ~u~ — hỏi giá trị của đỉnh ~u~.

Kết quả

Với mỗi truy vấn loại ~2~, in ra giá trị của đỉnh tương ứng trên một dòng.

Ví dụ

Đầu vào:

10 6
1 2
2 3
2 4
2 5
2 6
4 7
2 8
1 9
9 10
2 6
1 2 5
2 5
2 6
1 1 -5
2 1

Đầu ra:

0
5
5
-5

Giải thích: Ban đầu mọi đỉnh bằng ~0~. Sau khi cộng ~5~ vào cây con gốc ~2~, các đỉnh ~5~ và ~6~ đều bằng ~5~. Sau khi cộng ~-5~ vào cây con gốc ~1~ (toàn bộ cây), đỉnh ~1~ có giá trị ~-5~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u \le n~
• ~|v| \le 10^9~