Đề bài đã được chỉnh sửa để đảm bảo đúng với test.

Một tập đoàn lớn có ~N~ nhân viên. Hệ thống quản lý được cấu trúc theo dạng hình cây:

• Nhân viên thứ nhất là Tổng giám đốc.

• Mỗi nhân viên (ngoại trừ nhân viên thứ nhất) đều có đúng một người quản lý trực tiếp.

• Mọi nhân viên cấp dưới (trực tiếp hoặc gián tiếp) của nhân viên ~X~ đều thuộc "chi nhánh" do ~X~ lãnh đạo.

• Mỗi nhân viên có một điểm số đánh giá hiệu suất công việc ban đầu bằng ~0~. Có ~Q~ sự kiện xảy ra trong năm, thuộc ~2~ loại:

  • Loại ~1~: ~1~ ~U~ ~V~ - Tập đoàn thưởng ~V~ điểm hiệu suất cho nhân viên ~U~ và tất cả nhân viên thuộc chi nhánh do ~U~ lãnh đạo.

  • Loại ~2~: ~2~ ~U~ - Ban giám đốc cần thống kê tổng điểm hiệu suất của toàn bộ chi nhánh do ~U~ lãnh đạo bao gồm cả điểm của ~U~.

Yêu cầu: Hãy lập trình trả lời nhanh các truy vấn loại ~2~.

Input

• Dòng ~1~: Hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 2 \times 10^5)~.

• ~N - 1~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~U~ và ~V~ mô tả một mối quan hệ giữa nhân viên ~U~ và nhân viên ~V~. Đảm bảo cấu trúc là một cây với gốc là ~1~.

• ~Q~ dòng tiếp theo: Mỗi dòng bắt đầu bằng loại truy vấn ~1~ hoặc ~2~.

  • Nếu là ~1~, theo sau là ~U~ và ~V~ ~(1 \le U \le N, 1 \le V \le 1000)~.

  • Nếu là ~2~, theo sau là ~U~ ~(1 \le U \le N)~.

Output

Với mỗi truy vấn loại ~2~, in ra kết quả trên một dòng.

Scoring

Sample Input 1

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

Sample Output 1

30
45

Sample Input 2

4 3
1 2
2 3
3 4
1 3 20
2 2
2 4

Sample Output 2

40
20

Notes

Với ví dụ thứ nhất:

• Truy vấn ~1~ ~(1\ 2\ 10)~: Cấp ~10~ điểm cho nhánh do NV ~2~ quản lý (gồm NV ~2, 4, 5~).

• Truy vấn ~2~ ~(2\ 1)~: Tính tổng nhánh ~1~ (toàn công ty). Có ~3~ người mang ~10~ điểm, tổng ~= 30~.

• Truy vấn ~3~ ~(1\ 1\ 5)~: Cấp ~5~ điểm cho toàn công ty. Lúc này NV ~2, 4, 5~ có ~15~ điểm; NV ~1, 3~ có ~5~ điểm.

• Truy vấn ~4~ ~(2\ 2)~: Tính tổng nhánh ~2~. Gồm NV ~2~ ~(15)~ + NV ~4~ ~(15)~ + NV ~5~ ~(15) = 45~.

Với ví dụ thứ hai, cấu trúc công ty là đường thẳng: ~1~ quản lý ~2~, ~2~ quản lý ~3~, ~3~ quản lý ~4~.

• Truy vấn ~1~ ~(1\ 3\ 20)~: Thưởng ~20~ điểm cho chi nhánh của NV ~3~ (gồm NV ~3~ và ~4~).

• Truy vấn ~2~ ~(2\ 2)~: Tính tổng nhánh ~2~ (gồm NV ~2, 3, 4~). NV ~2~ là ~0~, NV ~3~ và ~4~ mỗi người ~20~. Tổng ~= 40~.

• Truy vấn ~3~ ~(2\ 4)~: Tính tổng nhánh ~4~ (chỉ có NV ~4~). Tổng ~= 20~.