题目描述

你那位富有的朋友 Erika 生活在一个有 $N$ 个村庄的国家，第 $i$ 个村庄有 $A_i$ 名居民。村庄之间通过 $N-1$ 条道路相连，利用这些道路可以从任意一个村庄到达任意另一个村庄。

忙碌了一整天后，Erika 精疲力竭，需要去度假，于是她计划访问这个国家的一些村庄。和所有有钱人一样，你的朋友最喜欢的事情就是送钱！因此，她打算带上一大袋硬币，在她访问的每个村庄（包括起始村庄）尽可能多地派发金钱。

不过有个问题：如果同一村庄里有居民拿到的钱比另一个居民少，他们会非常生气，Erika 的生命将受到威胁。为避免这种情况，她决定在 同一村庄 内尽可能多地给所有居民相同的金额，即使这意味着所有人都拿不到钱。

现在，Erika 想知道在这样一次旅行结束时她还会剩下多少钱。她会向你提出 $Q$ 个问题，每个问题的形式为：已知旅行从村庄 $u$ 出发，携带 $x$ 枚硬币，最终到达村庄 $v$，问旅行结束时还剩下多少硬币？

注意，旅行总是沿着两个村庄之间的简单路径进行，也就是唯一的最短路径。Erika 只会发放整枚硬币，因此她给每位居民的钱始终是非负整数。

输入格式

第一行包含两个整数 $N$（$1 \le N \le 2 \cdot 10^5$）和 $Q$（$1 \le Q \le 10^5$）。

接下来有 $N-1$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le N$）。这表示在村庄 $a_i$ 与村庄 $b_i$ 之间有一条道路。

下一行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（每个 $A_i$ 满足 $1 \le A_i \le 10^9$），表示第 $i$ 个村庄的居民数量。

最后有 $Q$ 行，每行对应一个查询。第 $i$ 行由整数 $u_i, v_i, x_i$ 组成（$1 \le u_i, v_i \le N$, $1 \le x_i \le 10^9$），其中 $u_i$ 是起始村庄，$v_i$ 是终点村庄，$x_i$ 是第 $i$ 个查询中 Erika 起始携带的硬币数量。

输出格式

对于每个查询，单独输出一行答案。

10 7
1 2
2 5
5 3
2 6
6 7
7 8
7 10
1 4
1 9
5 8 10 10 9 5 10 20 3 20
8 10 31
3 9 5
3 9 14
8 3 34
1 6 8
7 2 19
10 4 43

1
0
1
4
3
4
3

4 3
1 2
3 2
3 4
5 2 7 4
1 1 9
3 2 11
2 3 11

4
0
1

提示

样例解释

样例 $1$ 解释

在样例 $1$ 中，第一次旅行发生在村庄 $8$ 与村庄 $10$ 之间，Erika 起始有 $31$ 枚克朗。在第一个村庄（有 $20$ 名居民）她给每人 $1$ 枚克朗，还剩 $11$ 枚。随后旅程前往有 $10$ 名居民的村庄 $7$。在这里她同样给每人 $1$ 枚克朗，此时只剩 $1$ 枚。最后，Erika 到达有 $20$ 名居民的村庄 $10$。不幸的是，Erika 已经负担不起给这里的居民发钱了，因此最终她还剩 $1$ 枚克朗。

样例 $2$ 解释

样例 $2$ 满足子任务 $1\sim 3$ 的限制。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $10$ | $N, Q \le 2000$ | | $2$ | $20$ | 对所有 $1 \le i \le N-1$，存在村庄 $i$ 与村庄 $i+1$ 之间的路径，且 $A_i \le 100$。 | | $3$ | $25$ | 对所有 $1 \le i \le N-1$，存在村庄 $i$ 与村庄 $i+1$ 之间的路径。 | | $4$ | $25$ | 所有旅行都以村庄 $1$ 结束。形式化地，所有 $1 \le i \le Q$ 都有 $v_i = 1$。 | | $5$ | $20$ | 无额外限制。 |