市长 Mirko 居住的城市有 $n$ 个社区，由 $n-1$ 条双向道路连接，使得从任何一个社区出发都能到达其他所有社区。

Mirko 想要升级一些道路以缓解交通压力。对于每一条道路，我们已知其当前的车辆行驶速度 $v_i$、升级费用 $c_i$ 以及升级后的行驶速度 $s_i$。

有 $q$ 位不满的市民前来拜访 Mirko。每位市民都提出了一个升级建议。第 $i$ 位市民的建议是：“我们应该投入 $e_i$ 欧元用于升级社区 $a_i$ 和 $b_i$ 之间的道路。”

对于每一项建议，Mirko 感兴趣的是：如果他花费至多 $e_i$ 欧元来升级道路，在目标是最大化社区 $a_i$ 和 $b_i$ 之间路径上的最小行驶速度的前提下，这条路径上的最小行驶速度是多少。

Mirko 很快意识到这并不是一项简单的任务，于是雇佣你来帮助他！

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100,000$)，表示社区的数量。

接下来的 $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 100,000$)，表示不满的市民数量。

接下来的 $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}$)，描述了第 $i$ 位市民的建议。

输出格式

在 $q$ 行中，第 $i$ 行输出第 $i$ 位市民请求的答案。

子任务

样例

输入格式 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

输出格式 1

7
5
11

输入格式 2

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

输出格式 2

6
7
5
7

说明

第一个样例的说明：

插图展示了该城市及其社区。边上分别标注了当前的行驶速度、升级费用和升级后的速度。

如果我们升级 1 和 2 之间以及 1 和 3 之间的道路，从 2 到 4 的行驶速度将分别为 10、9 和 7 m/s。最小值为 7 m/s。

如果我们升级 4 和 3 之间的道路，从 6 到 4 的行驶速度将分别为 5 和 15 m/s。最小值为 5 m/s。

如果我们升级 3 和 5 之间的道路，从 5 到 3 的行驶速度将为 11 m/s。