题目背景

卡评测封号。

题目描述

市长 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

提示

样例解释 $1$：下图展示了这个城市和社区。边上写的分别是目前汽车的行驶速度，升级花费和升级后的汽车行驶速度。

如果我们升级 $1$ 和 $2$，$1$ 和 $3$ 之间的道路，从 $2$ 到 $4$ 的行驶速度将变成 $10,9,7$。最小为 $7$。

如果我们升级 $4$ 和 $3$ 之间的道路，从 $6$ 到 $4$ 的行驶速度将变成 $5,15$。最小为 $5$。

如果我们升级 $3$ 和 $5$ 之间的道路，从 $5$ 到 $3$ 的行驶速度将变成 $11$。