Một trong những thách thức lớn nhất sau khi kết hôn là quyết định xem ai sẽ làm công việc nhà nào trong gia đình. Cô dâu và chú rể may mắn của chúng ta đã quyết định giải quyết từng câu hỏi này bằng cách chơi một trò chơi.

Họ sẽ chơi nhiều phiên bản khác nhau của trò chơi. Các phiên bản của trò chơi sẽ được chơi trên cùng một cây có trọng số. Cây có \(N\) đỉnh, được đánh số từ \(1\) đến \(N\). Mỗi cạnh của cây được thể hiện bởi 3 số nguyên \(u, v, w\) thể hiện cạnh nối đỉnh \(u\) và đỉnh \(v\) có trọng số là \(w\).

Đối với mỗi trò chơi, cô dâu và chú rể sẽ chọn bốn thông số: \((U, V, hi, lo)\). Trò chơi sẽ được chơi trên con đường từ đỉnh \(U\) đến đỉnh \(V\) trong cây. Người chơi sẽ phủ lên một số cạnh của con đường này bằng các thẻ.

Các người chơi luân phiên thay phiên nhau, bắt đầu từ cô dâu. Trong mỗi lượt, người chơi hiện tại phải chọn một cạnh trên đường đi chưa có đặt thẻ và đặt thẻ vào cạnh đó.

Trong suốt trò chơi, người chơi duy trì một giá trị duy nhất được gọi là \(X\). Vào đầu trò chơi \(X = hi\). Khi một người chơi chọn một cạnh, họ phải chọn một cạnh có trọng số không lớn hơn \(X\). Khi đặt thẻ vào cạnh đó, \(X\) sẽ thay đổi bằng trọng số của cạnh đó.

Người chơi không thể thực hiện một nước đi hợp lệ sẽ thua cuộc. Ngoài ra, người chơi buộc phải đặt \(X\) nhỏ hơn \(lo\) (bằng cách đặt một thẻ lên một cạnh có trọng lượng nhỏ hơn \(lo\)) sẽ thua trò chơi.

Có \(Q\) truy vấn, mỗi truy vấn có dạng \((U, V, hi)\). Đối với mỗi truy vấn, bạn hãy in ra số giá trị \(lo\) trong phạm vi \([0, hi]\) để chú rể sẽ thắng trò chơi nếu cả cô dâu và chú rể đều chơi tối ưu.

Input:

• Dòng đầu tiên là số nguyên \(T\) - số thứ tự subtask

• Dòng thứ 2 chứa số nguyên \(N\) \((1 \leq N \leq 3 \cdot 10^5)\)

• \(N - 1\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u, v, w\) \((1 \leq u, v \leq N, u \neq v, 1 \leq w \leq N)\) thể hiện 1 cạnh của cây.

• Dòng tiếp theo chứa số nguyên \(Q\) \((1 \leq Q \leq 6 \cdot 10^5)\) thể hiện số truy vấn

• \(Q\) dòng cuối cùng, dòng thứ \(i\) chứa 3 số nguyên \(U, V, hi\) \((1 \leq U, V \leq N, 1 \leq hi \leq N)\)` thể hiện truy vấn thứ \(i\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) thể hiện kết quả của truy vấn thứ \(i\).

Scoring

• Subtask 1 (18 điểm): \(N \leq 40, Q \leq 200\)
• Subtask 2 (20 điểm): \(N \leq 700\)
• Subtask 3 (22 điểm): Cây có dạng đường thẳng
• Subtask 4 (20 điểm): \(N \leq 10^5, Q \leq 2 \cdot 10^5\).
• Subtask 5 (20 điểm): Không có ràng buộc gì thêm.

Example