Cho một cây gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\). Với hai đỉnh \(x\) và \(y\) bất kỳ trên cây, gọi \(d(x, y)\) là số cạnh trên đường đi chứa ít cạnh nhất từ \(x\) tới \(y\).

Với mỗi đỉnh \(r\) và cặp đỉnh \((x, y)\) trên cây, ta gọi \(f_r(x, y)\) là đỉnh \(p\) trên cây thỏa mãn:

• \(d(r, x) = d(r, p) + d(p, x)\)
• \(d(r, y) = d(r, p) + d(p, y)\)
• \(p\) là đỉnh có \(d(r, p)\) nhỏ nhất trong tất cả các đỉnh \(p\) thỏa mãn đồng thời hai điều kiện trên.

Dễ thấy rằng, giá trị \(f_r(x, y)\) luôn tồn tại và được xác định duy nhất với định nghĩa trên.

Với một đỉnh \(r\) cho trước, thầy giáo T liệt kê tất cả \(n^2\) bộ ba có dạng \((x, f_r(x, y), y)\) với mọi \(1 \le x, y \le n\). Sau đó, thầy sắp xếp các bộ ba này theo thứ tự từ điển. Nhắc lại, bộ ba \((a_1, a_2, a_3)\) có thứ tự từ điển nhỏ hơn bộ ba \((b_1, b_2, b_3)\) khi và chỉ khi một trong ba điều kiện sau thỏa mãn:

• \(a_1 < b_1\)
• \(a_1 = b_1\) và \(a_2 < b_2\)
• \(a_1 = b_1, a_2 = b_2\) và \(a_3 < b_3\)

Thầy T đưa ra \(q\) câu đố thuộc một trong hai dạng sau:

• 1 r x y: Tìm vị trí của bộ ba \((x, f_r(x, y), y)\) trong dãy sau khi sắp xếp theo quy trình trên.
• 2 r k: Tìm bộ ba ở vị trí thứ \(k\) trong dãy sắp xếp ở trên.

Bạn hãy giúp bạn A trả lời \(q\) câu đố này nhé.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)) lần lượt là số đỉnh của cây và số câu đố.
• \(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 cạnh của cây.
• \(q\) dòng tiếp theo, dòng thứ \(i\) thể hiện một câu đố thuộc một trong hai dạng sau:
  • 1 r x y với \(1 \le r, x, y \le n\).
  • 2 r k với \(1 \le r, \sqrt{k} \le n\).

Output

• In ra \(q\) dòng, dòng thứ \(i\) là câu trả lời của câu đố thứ \(i\).
• Nếu câu đố thứ \(i\) thuộc loại 1, in ra một số nguyên là thứ tự của bộ \((x, f_r(x, y), y)\).
• Nếu câu đố thứ \(i\) thuộc loại 2, in ra hai số nguyên \(x\) và \(y\) thể hiện bộ thứ \(k\) là \((x, f_r(x, y), y)\).

Example

5 2
1 2
1 3
2 4
2 5
1 2 3 4
2 2 13

13
3 4

Scoring

• Subtask \(1\) (\(11\%\) số điểm): \(n \le 300\).
• Subtask \(2\) (\(12\%\) số điểm): \(n, q \le 3000\).
• Subtask \(3\) (\(13\%\) số điểm): với mỗi đỉnh của cây không có quá hai đỉnh kết nối với nó.
• Subtask \(4\) (\(15\%\) số điểm): khoảng cách giữa hai đỉnh bất kỳ trên cây không vượt quá \(40\).
• Subtask \(5\) (\(16\%\) số điểm): không có câu đố loại 1.
• Subtask \(6\) (\(16\%\) số điểm): không có câu đố loại 2.
• Subtask \(7\) (\(17\%\) số điểm): không có rằng buộc gì thêm.