题目描述

Supervin 非常喜欢吃糖果。今天，他最喜欢的糖果店提供了 $N$ 颗糖果，它们排成一行。这一行中的第 $i$ 颗糖果（从 $1$ 开始计数）的甜度为 $S_i$。注意，糖果的甜度可能是负数，这意味着糖果尝起来是苦的。

Supervin 喜欢吃甜糖果。然而，总甜度超过 $D$ 的糖果对他来说也会太甜了。Supervin 还意识到，甜度为奇数的糖果是“奇怪的”，他不想吃超过 $O$ 颗奇怪的糖果。换句话说，奇糖果是指甜度不能被 $2$ 整除的糖果。此外，由于 Supervin 赶时间，他只能吃连续的一段糖果。

因此，他想吃一段连续的非空糖果子集，使得其中奇糖果的数量不超过 $O$，且总甜度最大化，但不超过 $D$。请帮助 Supervin 确定他能获得的最大总甜度，如果不存在满足这些约束的连续子集，则输出 IMPOSSIBLE。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含两行。第一行包含三个整数 $N$、$O$ 和 $D$，含义如上所述。第二行包含七个整数 $X_1$、$X_2$、$A$、$B$、$C$、$M$、$L$；这些值用于生成 $S_i$，生成方式如下：

定义：

• 对于 $i = 3$ 到 $N$，$X_i = (A \times X_{i-1} + B \times X_{i-2} + C) \bmod M$。
• 对于 $i = 1$ 到 $N$，$S_i = X_i + L$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Supervin 能获得的最大总甜度，如果不存在满足题目约束的连续子集，则输出 IMPOSSIBLE。

2
6 1 1000000000000000
1 1 1 1 0 100 0
6 1 -100
1 1 1 1 0 100 0

Case #1: 13
Case #2: IMPOSSIBLE

3
10 1 8
4 3 4 1 5 20 -10
10 2 8
4 3 4 1 5 20 -10
10 1 8
4 3 4 1 5 20 -19

Case #1: 7
Case #2: 8
Case #3: -5

提示

在样例 #1 中，生成的甜度数组 $S_i$ 为：[$1$、$1$、$2$、$3$、$5$、$8$]，其中加粗并带下划线的数字是奇数。由于 Supervin 只能吃一颗奇糖果，他可以通过取第五颗和第六颗糖果获得最大总甜度。

在样例 #2 中，生成的甜度数组 $S_i$ 与样例 #1 相同。然而，这次 Supervin 不能吃总甜度超过 $-100$ 的糖果，因此没有连续的糖果子集满足约束。

注意：对于本题的大数据集，我们不建议使用解释型/较慢的语言。

限制条件

$1 \le T \le 100$。

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

$0 \le O \le N$。

$-10^{15} \le D \le 10^{15}$。

$0 \le X_1, X_2, A, B, C \le 10^9$。

$1 \le M \le 10^9$。

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

$L = 0$。

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

$-5 \times 10^8 \le L \le 0$。

翻译由 DeepSeek V4 Pro 完成