Đất nước xinh đẹ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 ~v_i~, chi phí để nâng cấp đường là ~c_i~, sau nâng cấp thi 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 đ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 ~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 tiên chứa số nguyên ~n~ (~2 ≤ n ≤ 10^5~) là số thành phố;

Dòng thứ ~i~ trong ~n - 1~ dòng tiếp theo có ~5~ số nguyên ~x_i, y_i, v_i, c_i, s_i~ (~1 ≤ x_i, y_i ≤ n, 1 ≤ v_i < s_i ≤ 10^9, 1 ≤ c_i ≤ 10^9~), thể hiện thông tin hai thành phố ~x_i~ và ~y_i~ có đường nối trực tiếp, tốc độ chạy xe hiện tại là ~v_i~, chi phí nâng cấp đường là ~c_i~, tốc độ chạy xe sau nâng cấp là ~s_i~

Dòng tiếp theo chứa số nguyên ~Q~ (~1 ≤ Q ≤ 10^5~) là số giả định nâng cấp; Dòng thứ ~i~ trong Q dòng tiếp theo chứa ba số nguyên ~a_i, b_i, m_i~ (~1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ m_i ≤ 10^18~) mô tả giả định nâng cấp thứ ~i~.

Output

Gồm ~Q~ dòng, 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 2 thành phố ~a_i, b_i~ sau nâng cấp.

Test mẫu

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

Output

7
5
11

Giải thích: Giải thích ví dụ: 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í là 15, nên không 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 lớn 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 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.

Scoring

Subtask 1 (~40\%~): ~2 ≤ n, q ≤ 1000~

Subtask 2 (~30\%~): Mỗi thành phố được nối không quá 2 thành phố khác;

Subtask 3 (~30\%~): Không có ràng buộc thêm.

```