Tý có một mạng lưới viễn thông gồm \(N\) trạm phát sóng được kết nối với nhau bởi \(N-1\) đường cáp quang (cấu trúc cây). Các trạm được đánh số từ \(1\) đến \(N\), và các đường cáp được đánh số từ \(1\) đến \(N-1\). Mỗi đường cáp \(i\) có băng thông \(b_i\). Có \(Q\) thao tác:

• 1 i val: Thay đổi băng thông của đường cáp thứ \(i\) thành \(val\).
• 2 u v: Tìm băng thông lớn nhất trên đường đi từ trạm \(u\) đến trạm \(v\) (chỉ xét các đường cáp).

Hãy giúp kỹ sư mạng xử lý các yêu cầu trên.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa ba số \(u, v, b_i\) mô tả đường cáp \(i\) nối trạm \(u\) và \(v\) với băng thông \(b_i\) (\(0 \le b_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác.

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra băng thông lớn nhất trên một dòng.

Ví dụ

Input:

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

Output:

6
10

Ràng buộc