PhuocThien, uou, p2o2HuaGiaBao và Prototype đang đứng trước một mạng lưới gồm \(n\) phòng và \(n-1\) hành lang, trong đó giữa hai phòng bất kỳ luôn có đúng một đường đi, vì vậy toàn bộ công trình tạo thành một cây có trọng số. Ban đầu mọi phòng đều có năng lượng \(0\).

Có \(q\) thao tác cần xử lý:

• Thao tác 1 x y: Gán lại năng lượng của phòng \(x\) thành \(y\).
• Thao tác 2 x: Tính tổng ảnh hưởng mà phòng \(x\) nhận được từ toàn bộ hệ thống, tức là:
  
  \[ \sum_{i=1}^{n} a_i \cdot dist(x,i) \]

Với mỗi truy vấn loại 2 x, hãy in ra đáp án tương ứng. Dữ liệu bảo đảm cây liên thông và không có chu trình. Mỗi hành lang có độ dài dương. Các truy vấn cập nhật luôn hợp lệ. Mạng lưới này được Prototype thiết kế để kiểm tra khả năng phản ứng của hệ thống trong thời gian thực. PhuocThien phụ trách phần bản đồ, uou phụ trách phần tín hiệu, còn Prototype và p2o2HuaGiaBao quan sát toàn bộ kết quả. Đây là một bài cần xử lý nhanh vì số lượng thao tác rất lớn. Hãy chú ý rằng tổng giá trị có thể vượt khỏi phạm vi 32-bit.

Input

• Dòng đầu chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 10^6\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le n\) và \(1 \le w \le 10^6\)).
• \(q+1\) dòng sau, mỗi dòng là một thao tác 1 x y hoặc 2 x.
• Ban đầu mọi giá trị \(a_i\) đều bằng \(0\).

Output

• Với mỗi truy vấn loại 2 x, in ra một dòng là giá trị \(\sum_{i=1}^{n} a_i \cdot dist(x,i)\).

Example

5 7
1 2 3
1 3 2
2 4 4
2 5 1
1 2 3
1 4 5
2 1
1 2 0
2 5
1 3 2
2 4
2 3

44
25
18
45