题目描述

译自 COCI 2022/2023 Contest #4 T4「Mreža」

市长 Mirko 住在一个有 $n$ 个社区的城市里，这 $n$ 个社区用 $n-1$ 条双向道路连接，满足从任何社区出发都可以到达任意其他社区。

Mirko 想升级一些道路以疏导交通。对于每条路，我们知道目前在这条路上汽车的行驶速度 $v_i$，升级所需花费 $c_i$ 和升级后在这条路上汽车的行驶速度 $s_i$。

有 $q$ 个不满意的市民来见 Mirko。每个人都有他们自己的升级建议。第 $i$ 个市民的建议是：「我们应该在升级社区 $a_i$ 和 $b_i$ 之间的道路上投资 $e_i$ 欧元。」

对于每个建议，Mirko 感兴趣的是，如果他的目标是使社区 $a_i$ 和 $b_i$ 之间的最低驾驶速度最大化，那么他在升级道路上最多花费 $e_i$ 欧元的话这个最低驾驶速度是多少。

Mirko 瞬间意识到这个问题不简单，并且他雇佣你来帮助他！

输入格式

第一行包含一个整数 $n\ (2\le n\le 10^5)$，表示社区总数。

接下来 $n-1$ 行，每行五个整数 $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)$，表示社区 $x_i$ 和 $y_i$ 之间有一条路相连，目前在这条路上汽车的行驶速度为 $v_i$，升级所需花费为 $c_i$，升级后在这条路上汽车的行驶速度为 $s_i$。

接下来一行一个整数 $q\ (1\le q\le 10^5)$，表示不满意的市民总数。

接下来 $q$ 行，每行三个整数 $a_i,b_i,e_i\ (1\le a_i,b_i\le n,a_i\neq b_i,1\le e_i\le 10^{18})$，意义如题目描述。

输出格式

输出 $q$ 行，表示对每个市民建议的答案。

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

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

数据范围与提示

详细子任务附加限制及分值如下表。