题目描述

给定一棵有 $N$ 个节点的树，节点编号为 $1$ 到 $N$。每条边都有一个非零自然数作为费用。

一次操作定义为：选择一条当前费用严格大于 $0$ 的边，并将这条边的费用减少 $1$。

对于树上的一个节点 $v$ 和一个自然数 $k$，定义 $f(v,k)$ 为：在最多进行 $k$ 次上述操作后，从节点 $v$ 到树中所有其他节点的路径费用之和的最小可能值。

也就是说，可以在整棵树上任选边进行至多 $k$ 次减费操作，使得以 $v$ 为起点到所有其他节点的距离总和尽可能小。

任务

给定 $Q$ 个询问，每个询问形如 $(v,k_1,k_2)$，其中 $v$ 是树上的一个节点，且 $k_1\le k_2$。

对于每个询问，计算

并输出结果对 $10^9+7$ 取模后的值。

输入格式

第一行包含整数 $N$，表示树的节点数。

接下来 $N-1$ 行，每行包含三个整数 $u,v,w$，表示节点 $u$ 与节点 $v$ 之间有一条费用为 $w$ 的边。

接下来一行包含整数 $Q$，表示询问数。

接下来 $Q$ 行，每行包含三个整数 $v,k_1,k_2$，表示一个询问。

输出格式

输出 $Q$ 行。每行输出对应询问的答案，按输入顺序排列。

数据范围

• $2\le N\le 200000$
• $1\le Q\le 400000$
• $1\le w\le 10^8$
• $0\le k_1\le k_2\le 10^{14}$

子任务

样例

输入

5
1 2 3
2 3 4
2 5 6
1 4 2
4
1 4 5
2 1 1
5 20 22
4 0 0

输出

21
16
0
27

样例解释

样例中的树有 $N=5$ 个节点，边权如图所示，共有 $Q=4$ 个询问。

第一个询问中：

• 当 $k=4$ 时，可以将边 $1-2$ 减少 $3$ 次，将边 $1-4$ 减少 $1$ 次，得到 $f(1,4)=11$；
• 当 $k=5$ 时，可以将边 $1-2$ 减少 $3$ 次，将边 $2-3$ 减少 $1$ 次，将边 $2-5$ 减少 $1$ 次，得到 $f(1,5)=10$。

因此第一个询问的答案为 $f(1,4)+f(1,5)=21$。

第二个询问中，将边 $1-2$ 减少 $1$ 次，可以得到 $f(2,1)=16$。

第三个询问中，对于 $20\le k\le 22$ 的所有 $k$，所有边权都可以被减少到 $0$，因此答案为 $0$。

第四个询问中，$k_1=k_2=0$，没有任何操作可用。从节点 $4$ 到其他节点的路径费用之和为 $2+5+9+11=27$。