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

Có ~q~ truy vấn, mỗi truy vấn thuộc một trong ba loại sau:

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

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

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 ~3~, 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
1 4 -1
2 5 -4
3 4 5
3 2 5
3 2 2
3 4 2
2 5 5
3 1 2
1 3 3
3 2 1

Đầu ra:

-5
-4
0
-1
0
0

Giải thích: Sau hai truy vấn đầu, ~v_4 = -1~ và ~v_5 = -4~. Đường đi ~4 \to 2 \to 5~ có tổng ~-1 + 0 + (-4) = -5~; đường đi ~2 \to 5~ có tổng ~-4~.

Giới hạn

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