Cho cây giao thông gồm \(N\) điểm nút, ban đầu lượng phương tiện ở tất cả các nút bằng 0. Hãy trả lời nhanh \(Q\) truy vấn thuộc hai loại:

• 1 u v x: Cộng thêm \(x\) lượng phương tiện vào tất cả các điểm nằm trên đường đi đơn nối giữa \(u\) và \(v\).
• 2 u: Lấy tổng lượng phương tiện hiện tại của tất cả các nút nằm trong cây con gốc \(u\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(2 \le N, Q \le 100000\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le N\)) thể hiện một con đường nối giữa \(u\) và \(v\).
• \(Q\) dòng tiếp theo mô tả các truy vấn dưới dạng 1 u v x (\(1 \le u, v \le N\), \(1 \le x \le 1000\)) hoặc 2 u (\(1 \le u \le N\)).

Kết quả ra

• Với mỗi truy vấn loại 2, in ra tổng lượng phương tiện của cây con gốc \(u\) trên một dòng mới.

Ví dụ

Input

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

Output

10
20