Cho cây có \(n\) đỉnh và có gốc tại \(1\). Trên mỗi đỉnh sẽ có một giá trị, ban đầu tất cả giá trị này đều là \(0\). Có \(q\) truy vấn thuộc một trong hai loại:

• "1 u x": Tăng giá trị các đỉnh trong cây con gốc \(u\) lên \(x\).
• "2 u x": Tăng giá trị đỉnh \(u\) lên \(x\).
• "3 u v": Tìm tổng các đỉnh trên đường đi đơn từ \(u\) đến \(v\).

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

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên \(n,q\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u,v\), thể hiện có cạnh nối giữa \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng gồm một truy vấn theo định dạng trên.

Dữ liệu ra

• In ra một số nguyên là đáp án cho mỗi truy vấn loại \(3\).

Điều kiện

• \(1 \le n,q \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(|x| \le 10^6\)

Input 1

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

Output 1

-5
-4
0
-1
0
0