题目描述

Supervin 教授了 $N$ 个班级，班级编号为 $1$ 到 $N$。在他最近一次考试后，他注意到每个班级中学生的考试成绩构成了一个连续整数序列。因此，Supervin 可以将第 $i$ 个班级的成绩总结为两个整数 $L_i$ 和 $R_i$。这意味着第 $i$ 个班级有 $R_i - L_i + 1$ 名学生，并且对于每个 $x$（$L_i \le x \le R_i$），恰好有一名学生的成绩为 $x$。

Supervin 希望将所有班级的学生成绩合并，并按非递增顺序排序。他有 $Q$ 个问题（编号为 $1$ 到 $Q$）关于这个列表；对于第 $i$ 个问题，他想知道第 $K_i$ 高的成绩是多少。（如果 $K_i$ 大于学生总数，则第 $i$ 个问题的答案为 $0$。）

你能帮助 Supervin 回答所有问题吗？由于答案可能很多，我们不输出所有答案，而是输出一个证明你已回答它们的结果：对于所有 $1 \le i \le Q$，计算 $(S_i \times i)$ 的和，其中 $S_i$ 是第 $i$ 个问题的答案。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含四行。第一行包含两个整数 $N$ 和 $Q$，如上所述。接下来的三行每行分别包含六个整数，格式如下：

• $X_1$ $X_2$ $A_1$ $B_1$ $C_1$ $M_1$
• $Y_1$ $Y_2$ $A_2$ $B_2$ $C_2$ $M_2$
• $Z_1$ $Z_2$ $A_3$ $B_3$ $C_3$ $M_3$

这些值用于生成 $L_i$、$R_i$ 和 $K_i$，生成方式如下：

定义：

• 对于 $i = 3$ 到 $N$：$X_i = (A_1 \times X_{i-1} + B_1 \times X_{i-2} + C_1) \bmod M_1$。
• 对于 $i = 3$ 到 $N$：$Y_i = (A_2 \times Y_{i-1} + B_2 \times Y_{i-2} + C_2) \bmod M_2$。
• 对于 $i = 3$ 到 $Q$：$Z_i = (A_3 \times Z_{i-1} + B_3 \times Z_{i-2} + C_3) \bmod M_3$。

同时定义：

• 对于 $i = 1$ 到 $N$：$L_i = \min(X_i, Y_i) + 1$。
• 对于 $i = 1$ 到 $N$：$R_i = \max(X_i, Y_i) + 1$。
• 对于 $i = 1$ 到 $Q$：$K_i = Z_i + 1$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有 $1 \le i \le Q$ 的 $(S_i \times i)$ 之和，其中 $S_i$ 是第 $i$ 个问题的答案。

2
5 1
3 1 4 1 5 9
2 7 1 8 2 9
4 8 15 16 23 42
7 1
2 3 4 5 6 31
1 3 4 5 5 17
2 2 1 3 2 100

Case #1: 7
Case #2: 28

2
5 5
3 1 4 1 5 9
2 7 1 8 2 9
4 8 15 16 23 42
1 2
0 0 0 0 0 1
0 0 0 0 0 1
0 1 0 0 0 2

Case #1: 39
Case #2: 1

提示

在样例 #1 中，生成的数组 X、Y、Z 为：

• $X = [3, 1, 3, 0, 8]$。
• $Y = [2, 7, 7, 2, 6]$。
• $Z = [4]$。

因此，

• $L = [3, 2, 4, 1, 7]$。
• $R = [4, 8, 8, 3, 9]$。
• $K = [5]$。

每个班级的学生成绩分别为：$[3, 4]$、$[2, 3, 4, 5, 6, 7, 8]$、$[4, 5, 6, 7, 8]$、$[1, 2, 3]$ 和 $[7, 8, 9]$。这意味着所有班级合并后的学生成绩为：$[3, 4, 2, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 1, 2, 3, 7, 8, 9]$。将它们按非递增顺序排序后为：$[9, 8, 8, 8, 7, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1]$。因此，第 $5$ 高的成绩为 $7$。于是 $S = [7]$，答案为 $7 \times 1 = 7$。

限制条件

$1 \le T \le 100$。

$1 \le N \le 4 \times 10^5$。

对于所有 $i$，$0 \le A_i < M_i$。

对于所有 $i$，$0 \le B_i < M_i$。

对于所有 $i$，$0 \le C_i < M_i$。

$0 \le X_1 < M_1$。

$0 \le X_2 < M_1$。

$0 \le Y_1 < M_2$。

$0 \le Y_2 < M_2$。

$0 \le Z_1 < M_3$。

$0 \le Z_2 < M_3$。

对于所有 $i$，$1 \le M_i \le 10^9$。

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

$Q = 1$。

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

$1 \le Q \le 10^5$。

翻译由 DeepSeek V4 Pro 完成