题目描述

Charles 是 Googleland 城市的一名卡车司机。Googleland 的结构是一棵有 $N$ 个节点的树，每个节点代表一个城市，每条边代表两个城市之间的道路。城市编号为 $1$ 到 $N$。Googleland 的首都是城市 $1$。每天，Charles 在城市 $C$ 装载重量为 $W$ 的货物，并希望沿城市间的唯一简单路径将货物运送到城市 $1$。每条道路 $i$ 设有一个通行费，如果货物重量大于或等于载重限制 $L_i$，则需支付金额 $A_i$。

Charles 工作 $Q$ 天，每天给出起点城市 $C$ 和货物重量 $W$。对于每天，求 Charles 当天支付的所有通行费的最大公约数。如果当天无需支付任何通行费，则答案为 $0$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$。

接下来的 $N-1$ 行描述道路。其中第 $i$ 行包含四个空格分隔的整数 $X$、$Y$、$L_i$ 和 $A_i$，表示连接城市 $X$ 和 $Y$ 的道路，其载重限制为 $L_i$，通行费为 $A_i$。

接下来的 $Q$ 行描述查询。其中第 $j$ 行包含两个空格分隔的整数 $C_j$ 和 $W_j$，表示第 $j$ 天的起点城市和货物重量。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是按顺序给出的 $Q$ 天答案列表，用空格分隔。

2
7 5
2 1 2 4
2 3 7 8
3 4 6 2
5 3 9 9
2 6 1 5
7 1 5 7
5 10
5 8
4 1
6 1
7 6
3 2
1 2 2 10
3 2 3 5
3 2
3 3

Case #1: 1 4 0 5 7
Case #2: 10 5

提示

在样例 #1 中：

• 第一天，Charles 需要支付道路 $(5, 3)$、$(3, 2)$ 和 $(2, 1)$ 的通行费。答案为 $\gcd(9, 8, 4) = 1$。
• 第二天，Charles 需要支付道路 $(3, 2)$ 和 $(2, 1)$ 的通行费。答案为 $\gcd(8, 4) = 4$。
• 第三天，Charles 无需支付任何通行费，因此答案为 $0$。

在样例 #2 中：

• 第一天，Charles 需要支付道路 $(2, 1)$ 的通行费。答案为 $10$。
• 第二天，Charles 需要支付道路 $(3, 2)$ 和 $(2, 1)$ 的通行费。答案为 $\gcd(5, 10) = 5$。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le L_i \le 2 \times 10^5$。

对于所有 $i$，$1 \le A_i \le 10^{18}$。

所有 $L_i$ 互不相同。

对于所有 $j$，$2 \le C_j \le N$。

对于所有 $j$，$1 \le W_j \le 2 \times 10^5$。

保证给定的道路构成一棵树。

测试集 1

$2 \le N \le 1000$。

$1 \le Q \le 1000$。

测试集 2

最多 $20$ 个测试用例满足 $2 \le N \le 5 \times 10^4$ 且 $1 \le Q \le 10^5$。

其余测试用例满足 $2 \le N \le 1000$ 且 $1 \le Q \le 1000$。

翻译由 DeepSeek V4 Pro 完成