Giao thông

Thị trưởng Long sống trong một thành phố gồm \(n\) khu vực dân cư được nối với nhau bởi \(n - 1\) con đường hai chiều,
sao cho từ bất kỳ khu vực nào cũng có thể đi đến mọi khu vực khác.

Long muốn nâng cấp một số con đường để cải thiện tình trạng giao thông. Với mỗi con đường,
ta biết tốc độ di chuyển hiện tại \(v_i\), chi phí nâng cấp \(c_i\) và tốc độ sau khi nâng cấp \(s_i\).

Có \(q\) người dân đến gặp Long với các đề xuất khác nhau.
Đề xuất của người dân thứ \(i\) là:
"Tôi muốn đầu tư \(e_i\) euro để nâng cấp một số con đường trên hành trình từ khu vực \(a_i\) đến khu vực \(b_i\)."

Với mỗi đề xuất, Long muốn biết:
nếu ông chi không quá \(e_i\) euro để chọn nâng cấp một số con đường trên đường đi từ \(a_i\) đến \(b_i\),
thì tốc độ nhỏ nhất trên toàn bộ hành trình này có thể được tăng lên đến bao nhiêu,
trong trường hợp ông lựa chọn nâng cấp tối ưu để tối đa hóa tốc độ nhỏ nhất đó.

\InputFile

Dòng đầu chứa số nguyên \(n\) (\(2 \le n \le 100\,000\)), số khu vực dân cư.

Mỗi dòng 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 < s_i \le 10^9\), \(1 \le c_i \le 10^9\)),
cho biết khu vực \(x_i\) và \(y_i\) được nối trực tiếp với nhau bằng một con đường có:
tốc độ hiện tại \(v_i\), chi phí nâng cấp \(c_i\), và tốc độ sau nâng cấp \(s_i\).

Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 100\,000\)), số đề xuất của người dân.

Mỗi dòng trong \(q\) dòng tiếp theo 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}\)),
diễn tả đề xuất thứ \(i\).

\OutputFile

Ở dòng thứ \(i\) trong \(q\) dòng, in ra đáp án cho đề xuất thứ \(i\),
tức là tốc độ nhỏ nhất lớn nhất có thể đạt được trên đường đi từ \(a_i\) đến \(b_i\)
nếu chỉ sử dụng tối đa \(e_i\) euro.

\Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 21 &
\(\, n, q \le 1000\)

2 & 29 &
Mỗi khu vực được nối với tối đa 2 khu vực khác

3 & 50 &
Không có ràng buộc bổ sung

\hline
\endtabular
\endcenter

\Examples

\beginexample
\exmp
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

7
5
11

\exmp
4
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 10

6
7
5
7

\endexample

\endproblem