P16647 [GKS 2018 #D] Candies

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`。

在样例 #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 完成