Problem Description

Supervin is teaching $N$ classes, which are numbered from $1$ to $N$. After giving his most recent exam, he noticed that in each of his classes, the test scores of his students form a sequence of consecutive integers. Therefore, Supervin can summarize the scores for the i-th class as two integers $L_i$ and $R_i$. This means that the i-th class has $R_i - L_i + 1$ students, and for each $x$ ($L_i \le x \le R_i$), there is exactly one student with score $x$.

Supervin would like to combine the scores from the students from all of his classes and sort the scores in non-increasing order. He has $Q$ questions (numbered from $1$ to $Q$) about this list; for the i-th question, he wants to know what the $K_i$-th highest score is. (If $K_i$ is greater than the number of students, then the answer for the i-th question is $0$.)

Can you help Supervin answer all of his questions? Since there may be many answers, instead of outputting all of them, output proof that you have answered them: the sum of $(S_i \times i)$ for all $1 \le i \le Q$, where $S_i$ is the answer to the i-th question.

Input Format

The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains four lines. The first line contains two integers N and Q as described above. The next three lines each contain six integers in the following format, respectively:

• $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$

These values are used to generate $L_i$, $R_i$, and $K_i$ as follows:

We define:

• $X_i = (A_1 \times X_{i - 1} + B_1 \times X_{i - 2} + C_1)$ modulo $M_1$, for i = 3 to N.
• $Y_i = (A_2 \times Y_{i - 1} + B_2 \times Y_{i - 2} + C_2)$ modulo $M_2$, for i = 3 to N.
• $Z_i = (A_3 \times Z_{i - 1} + B_3 \times Z_{i - 2} + C_3)$ modulo $M_3$, for i = 3 to Q.

We also define:

• $L_i = \min(X_i, Y_i) + 1$, for i = 1 to N.
• $R_i = \max(X_i, Y_i) + 1$, for i = 1 to N.
• $K_i = Z_i + 1$, for i = 1 to Q.

Output Format

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 sum of $(S_i \times i)$ for all $1 \le i \le Q$, where $S_i$ is the answer to the i-th question.

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

Hint

In Sample Case #1, the generated arrays X, Y, Z are:

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

Therefore,

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

The students' scores for each of the classes are $[3, 4]$, $[2, 3, 4, 5, 6, 7, 8]$, $[4, 5, 6, 7, 8]$, $[1, 2, 3]$, and $[7, 8, 9]$. This means that the students' scores for all classes combined are $[3, 4, 2, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 1, 2, 3, 7, 8, 9]$. If we sort them in non-increasing order, they are $[9, 8, 8, 8, 7, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1]$. Therefore, the student with the 5th highest score has score 7. Thus, $S = [7]$ and the answer is $7 \times 1 = 7$.

Limits

$1 \le T \le 100$.

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

$0 \le A_i < M_i$, for all i.

$0 \le B_i < M_i$, for all i.

$0 \le C_i < M_i$, for all 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$.

$1 \le M_i \le 10^9$, for all i.

Small dataset (Test set 1 - Visible)

$Q = 1$.

Large dataset (Test set 2 - Hidden)

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