Cho một cây gồm ~n~ đỉnh, gốc tại đỉnh ~1~. Mỗi đỉnh có một giá trị, ban đầu tất cả đều bằng ~0~.

Có ~q~ truy vấn thuộc ba loại sau:

1. ~1~ ~u~ — tính tổng giá trị các đỉnh trong cây con gốc ~u~.
2. ~2~ ~u~ — hỏi giá trị hiện tại của đỉnh ~u~.
3. ~3~ ~u~ ~v~ ~x~ — tăng giá trị của mọi đỉnh nằm trên đường đi đơn từ ~u~ tới ~v~ thêm ~x~.

Hãy trả lời các truy vấn loại ~1~ và ~2~.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~ và ~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 theo định dạng đã nêu.

Kết quả

Với mỗi truy vấn loại ~1~ hoặc ~2~, in ra đáp án trên một dòng.

Ví dụ

Đầu vào:

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

Đầu ra:

0
0
4
0
4
2
0
8

Giải thích: Truy vấn đầu cộng ~2~ vào các đỉnh ~2~ và ~4~. Khi đó cây con gốc ~2~ có tổng ~2 + 0 + 2 + 0 = 4~. Sau khi cộng ~4~ vào đỉnh ~4~ (đường đi ~4 \to 4~), cây con gốc ~2~ có tổng ~8~.

Giới hạn

• ~1 \le n, q \le 2 \cdot 10^5~
• ~1 \le u, v \le n~
• ~|x| \le 10^6~