Đất nước hình đẹp ABC có ~n~ thành phố lớn, có ~n - 1~ con đường cao tốc quan trọng, giữa hai thành phố bất kỳ đều có thể đến được nhau bằng các con đường cao tốc này. Cho biết con đường thứ ~i~ nối thành phố ~x_i, y_i~ có tốc độ chạy xe hiện tại tại ~v_i~, chi phí để nâng cấp đường là ~c_i~, sau nâng cấp thì tốc độ đạt được ~s_i~.

Tốc độ lưu thông giới hạn giữa hai thành phố ~u, v~ được tính bằng tốc độ nhỏ nhất của các đoạn trên đường nối chúng.

Nhằm phát triển kinh tế, người ta đã đưa ra ~Q~ giả định nâng cấp. Giả định thứ ~i~ cần sử dụng một khoản tiền không quá ~m_i~ để nâng cấp đường đi từ thành phố ~a_i~ đến ~b_i~.

Yêu cầu: Với mỗi giả định nâng cấp, hãy tính tốc độ lưu thông giới hạn lớn nhất có thể đạt được.

Input

• Dòng đầu chứa số nguyên ~n~ (~2 \le n \le 10^5~);
• Dòng thứ ~i~ trong ~n - 1~ dòng tiếp theo chứa ~5~ số nguyên ~x_i, y_i, v_i, c_i, s_i~ (~1 \le x_i, y_i \le n; 1 \le v_i \le s_i \le 10^9; 1 \le c_i \le 10^9~).
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 \le Q \le 10^5~);
• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i, m_i~ (~1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le m_i \le 10^{18}~) mô tả giả định nâng cấp thứ ~i~.

Output

Ghi ra ~Q~ dòng, mỗi dòng thứ ~i~ ghi số nguyên là tốc độ lưu thông giới hạn lớn nhất trên đường đi giữa hai thành phố ~a_i, b_i~ sau nâng cấp.

Sample Input

6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10

Sample Output

7
5
11

Mỗi đỉnh là một thành phố. Trên các cạnh viết thêm tốc độ lái xe hiện tại, chi phí nâng cấp và tốc độ sau khi nâng cấp.

• Giả định 1: Nâng cấp đường ~(1, 2)~ được tốc độ ~10~, chi phí ~7~. Nâng cấp đường ~(1, 3)~ được tốc độ ~9~, chi phí ~8~. Tổng chi phí ~15~, nên tốc độ nâng cấp tiếp được đường ~(3, 4)~. Đường đi giữa 2 và 4 có các tốc độ lần lượt là ~10, 9, 7~. Tốc độ lưu thông giới hạn nhỏ nhất đạt được là ~7~.
• Giả định 2: Số tiền không đủ để tăng tốc độ tối thiểu trên đoạn ~(3, 6)~ nên tốc độ lưu thông giới hạn lớn nhất là ~5~.
• Giả định 3: Nâng cấp ~(3, 5)~ để có tốc độ lưu thông giới hạn lớn nhất là ~11~.

Ràng buộc

• Subtask 1 (40% số điểm): Có ~2 \le n, Q \le 1000~;
• Subtask 2 (30% số điểm): Mỗi thành phố được nối không quá 2 thành phố khác;
• Subtask 3 (30% số điểm): Không có ràng buộc thêm.