An là thị trưởng thành phố lớn có ~n~ khu phố được kết nối với ~n - 1~ đường hai chiều sao cho từ bất kỳ khu dân cư nào cũng có thể đến được mọi nơi khu khác.

An muốn nâng cấp một số con đường để giảm lưu lượng giao thông. Đối với mỗi con đường, chúng ta biết tốc độ hiện tại xe ~v_i~ chạy trên đó, giá nâng cấp ~c_i~ và tốc độ lái xe sau khi nâng cấp ~s_i~.

Có ~q~ công dân không hài lòng đến thăm An. Mỗi người đều có gợi ý nâng cấp. Đề xuất của công dân thứ ~i~ là: Chúng ta nên đầu tư ~e_i~ đồng vào việc nâng cấp đường nối từ khu phố ~a_i~ đến phố ~b_i~.

Đối với mỗi đề xuất, An quan tâm đến tốc độ lái xe tối thiểu từ ~a_i~ đến ~b_i~ là bao nhiêu nếu anh ta chi tối đa ~e_i~ đồng để nâng cấp đường, vì mục tiêu của anh ta là tối đa hóa tốc độ lái xe tối thiểu từ ~a_i~ đến ~b_i~.

Yêu cầu: Bạn hãy giúp An trả lời cho yêu cầu của công dân thứ ~i~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 100000)~, số khu phố.

• Mỗi dòng trong ~n - 1~ dòng tiếp theo có ~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 < s_i \le 10^9, 1 \le c_i \le 10^9)~, biểu thị hai khu phố ~x_i~ và ~y_i~ liên thông, tốc độ chạy xe hiện tại là ~v_i~, chi phí nâng cấp đường là ~c_i~, và tốc độ trên đường sẽ là ~s_i~.

• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 100000)~, số lượng người dân không hài lòng.

• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a_i, b_i, e_i~ ~(1 \le a_i, b_i \le n, a_i \ne b_i, 1 \le e_i \le 10^{18})~, trong đó mô tả đề nghị của công dân thứ ~i~.

Output

• Ở dòng thứ ~i~ in câu trả lời cho yêu cầu của công dân thứ ~i~.

Scoring

Sample Input 1

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 1

7
5
11

Notes

Nếu chúng ta nâng cấp đường giữa ~1~ và ~2~ và giữa ~1~ và ~3~ thì tốc độ lái xe từ ~2~ lên ~4~ sẽ là ~10, 9~ và ~7~. Tối thiểu là ~7~.

Nếu chúng ta nâng cấp đường từ ~4~ đến ~3~ thì tốc độ lái xe từ ~6~ lên ~4~ sẽ là ~5~ và ~15~. Tối thiểu là ~5~.

Nếu chúng ta nâng cấp đường giữa ~3~ và ~5~ thì tốc độ lái xe từ ~5~ và ~3~ sẽ là ~11~.