P16647 [GKS 2018 #D] Candies

Supervin loves to eat candies. Today, his favorite candy shop is offering $N$ candies, which are arranged in a line. The $i$-th candy in the line (counting starting from 1) has a sweetness level $S_i$. Note that the sweetness level of a candy might be negative, which means the candy tastes bitter. Supervin likes to eat sweet candies. However, candies with a combined sweetness level of more than $D$ would be too much sweetness even for him. Supervin also realises that a candy with an odd sweetness level is "odd", and he does not want to eat more than $O$ odd candies. In other words, an odd candy is a candy with a sweetness level that is not evenly divisible by 2. Additionally, since Supervin is in a rush, he can only eat a single contiguous subset of candies. Therefore, he wants to eat a contiguous non-empty subset of candies in which there are at most $O$ odd candies and the total sweetness level is maximized, but not more than $D$. Help Supervin to determine the maximum total sweetness level he can get, or return `IMPOSSIBLE` if there is no contiguous subset satisfying these constraints.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains two lines. The first line contains three integers $N$, $O$, and $D$, as described above. The second line contains seven integers $X_1$, $X_2$, $A$, $B$, $C$, $M$, $L$; these values are used to generate the values $S_i$, as follows: We define: * $X_i = ( A \times X_{i-1} + B \times X_{i-2} + C ) \pmod M$, for $i = 3$ to $N$. * $S_i = X_i + L$, for $i = 1$ to $N$.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sweetness level Supervin can get, or `IMPOSSIBLE` if there is no possible contiguous subset satisfying the problem constraints.

In Sample Case #1, the generated array of sweetness values $S_i$ is: [**$1$**, **$1$**, $2$, **$3$**, **$5$**, $8$], where the bold and underlined numbers are the odd numbers. Since Supervin can only eat one odd candy, he can get a maximum total sweetness level by taking the fifth and the sixth candies. In Sample Case #2, the generated array of sweetness values $S_i$ is the same as in Sample Case #1. However, this time Supervin cannot eat candies with a total sweetness level of more than $-100$, so no contiguous subset of candies satisfies the constraints. **Note**: We do not recommend using interpreted/slower languages for the Large dataset of this problem. ### Limits $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$. **Small dataset (Test set 1 - Visible)** $L = 0$. **Large dataset (Test set 2 - Hidden)** $-5 \times 10^8 \le L \le 0$.