#214122. [POCamp 2023] 送钱 / The Generous Traveler

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

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

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

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

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

第一行包含两个整数 （）和 （）。

接下来有 行，第 行包含两个整数 和 （）。这表示在村庄 与村庄 之间有一条道路。

下一行包含 个整数 （每个 满足 ），表示第 个村庄的居民数量。

最后有 行，每行对应一个查询。第 行由整数 组成（, ），其中 是起始村庄， 是终点村庄， 是第 个查询中 Erika 起始携带的硬币数量。

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

样例输入 1

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

1
0
1
4
3
4
3

样例输入 2

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

样例输出 2

4
0
1

样例解释

样例 解释

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

样例 解释

样例 满足子任务 的限制。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | | | | | | | 对所有 ，存在村庄 与村庄 之间的路径，且 。 | | | | 对所有 ，存在村庄 与村庄 之间的路径。 | | | | 所有旅行都以村庄 结束。形式化地，所有 都有 。 | | | | 无额外限制。 |