题目描述

:::align{center} :::

为了在击败邪恶的 Graphendorf 的征途中前进，我们的英雄 Edge 必须在一座神殿中克服一项挑战。神殿位于 xy 平面中的二维空间，沿 x 轴竖立着 $N$ 座高度各不相同的塔。每座塔可以用二维平面中的一条垂直线段表示。对于第 $i$ 座塔，塔的底部位于 $(p_i, 0)$，塔的顶部位于 $(p_i, h_i)$。此外，还有 $K$ 个气球漂浮在平面中。每个气球可以用二维平面中的一个点表示，第 $i$ 个气球位于 $(x_i, y_i)$。Edge 必须在这项挑战中收集尽可能多的气球。

幸运的是，Edge 有一个可靠的运动滑翔伞，是他在神殿另一个房间中找到的。他可以选择爬上任意一座塔，并从塔上的任意位置向 x 轴的正方向或负方向滑翔下降。当他滑翔时，他沿着一条与塔身成 $45$ 度角的直线路径下降。Edge 在从塔上滑下时，可以收集沿途的任何气球。他可以重复这个过程，任意多次地爬上塔并跳下。如果他在下降过程中碰到一座塔，那么我们认为他在该点位于塔上并可以开始攀爬。你可以假设 Edge 是 xy 平面中的一个点。

借助一副由古代科技制成的护目镜，Edge 能够得知每座塔和每个气球的高度与位置。有了这些信息，你能帮助 Edge 推算出他在这座神殿中最多可以收集多少个气球吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含五行。第一行包含上述的整数 $N$ 和 $K$。接下来的四行各自描述一个用于生成塔的位置、高度以及气球的 $x$、$y$ 坐标的递推式。这四行的格式如下，每行包含六个整数：

• $p_1\ p_2\ A_1\ B_1\ C_1\ M_1$
• $h_1\ h_2\ A_2\ B_2\ C_2\ M_2$
• $x_1\ x_2\ A_3\ B_3\ C_3\ M_3$
• $y_1\ y_2\ A_4\ B_4\ C_4\ M_4$

为了生成 $p_i$（$i = 3$ 到 $N$）、$h_i$（$i = 3$ 到 $N$）、$x_i$（$i = 3$ 到 $K$）和 $y_i$（$i = 3$ 到 $K$）的值，我们使用以下递推式：

• 对于 $i = 3$ 到 $N$：$p_i = (A_1 \times p_{i-1} + B_1 \times p_{i-2} + C_1) \bmod M_1 + 1$。
• 对于 $i = 3$ 到 $N$：$h_i = (A_2 \times h_{i-1} + B_2 \times h_{i-2} + C_2) \bmod M_2 + 1$。
• 对于 $i = 3$ 到 $K$：$x_i = (A_3 \times x_{i-1} + B_3 \times x_{i-2} + C_3) \bmod M_3 + 1$。
• 对于 $i = 3$ 到 $K$：$y_i = (A_4 \times y_{i-1} + B_4 \times y_{i-2} + C_4) \bmod M_4 + 1$。

保证没有两座塔的位置相同。然而，塔与气球有可能重叠。在这种情况下，我们认为气球可以被收集。注意，多个气球可能共享同一个点；此时，Edge 经过该点即可同时收集所有这些气球。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Edge 可以收集到的最大气球数量。

2
3 2
1 4 1 1 0 11
4 1 1 1 8 11
2 5 0 0 0 11
4 1 0 0 0 11
5 5
2 4 1 0 1 13
4 4 0 1 12 13
1 4 1 1 0 13
3 5 1 1 7 13

Case #1: 1
Case #2: 4

提示

注意，样例 #1 的输入生成的就是题目描述中所描绘的场景。生成的数组为：

• $p = [1, 4, 6]$
• $h = [4, 1, 3]$
• $x = [2, 5]$
• $y = [4, 1]$

在样例 #2 中，生成的数组为：

• $p = [2, 4, 6, 8, 10]$
• $h = [4, 4, 4, 4, 4]$
• $x = [1, 4, 6, 11, 5]$
• $y = [3, 5, 3, 3, 1]$

限制条件

$1 \le T \le 100$。

对于 $i = 1$ 到 $4$，$0 \le A_i \le 10^9$。

对于 $i = 1$ 到 $4$，$0 \le B_i \le 10^9$。

对于 $i = 1$ 到 $4$，$0 \le C_i \le 10^9$。

对于 $i = 1$ 到 $4$，$1 \le M_i \le 10^9$。

$1 \le p_1, p_2 \le 10^9$。

$1 \le h_1, h_2 \le 10^9$。

$1 \le x_1, x_2 \le 10^9$。

$1 \le y_1, y_2 \le 10^9$。

对于 $i, j = 1$ 到 $N$，$i \ne j$，有 $p_i \ne p_j$。

小数据集（测试集 1 – 可见）

$2 \le N \le 1000$。

$2 \le K \le 1000$。

大数据集（测试集 2 – 隐藏）

$2 \le N \le 10^5$。

$2 \le K \le 10^5$。

翻译由 DeepSeek V4 Pro 完成