Cho một cây \(n\) đỉnh và \(q\) câu truy vấn. Truy vấn có 2 dạng:

• Dạng \(1\): Tính khoảng cách đỉnh \(u\) đến \(v\)
• Dạng \(2\): Tìm đỉnh thứ \(k\) trên đường đi từ \(u\) đến \(v\).

Dữ liệu vào

• Dòng đầu tiên chứa 2 số nguyên \(n,q\) số đỉnh và số câu truy vấn. \((1 \le n,q \le 10^5)\)
• \(n-1\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u,v,w\) là cạnh nối đỉnh \(u\) và \(v\) có trọng số là \(w\).
• \(q\) dòng tiếp theo, mỗi dòng có \(3\) hoặc \(4\) số nguyên \(t,u,v,k\). \(t=1\) là câu truy vấn dạng \(1\), \(t=2\) là câu truy vấn dạng \(2\). Đối với câu truy vấn dạng \(2\) thì sẽ có thêm \(k\).

Dữ liệu vào

• \(q\) dòng là đáp án của \(q\) truy vấn.

Input 1

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

Output 1

5
3