Combining Classes

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 Li and Ri. This means that the i-th class has Ri - Li + 1 students, and for each x (Li ≤ x ≤ Ri), 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 Ki-th highest score is. (If Ki 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 (Si × i) for all 1 ≤ i ≤ Q, where Si is the answer to the i-th question.

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:

• X1 X2 A1 B1 C1 M1
• Y1 Y2 A2 B2 C2 M2
• Z1 Z2 A3 B3 C3 M3

These values are used to generate Li, Ri, and Ki as follows:

We define:

• Xi = (A1 × Xi - 1 + B1 × Xi - 2 + C1) modulo M1, for i = 3 to N.
• Yi = (A2 × Yi - 1 + B2 × Yi - 2 + C2) modulo M2, for i = 3 to N.
• Zi = (A3 × Zi - 1 + B3 × Zi - 2 + C3) modulo M3, for i = 3 to Q.

We also define:

• Li = min(Xi, Yi) + 1, for i = 1 to N.
• Ri = max(Xi, Yi) + 1, for i = 1 to N.
• Ki = Zi + 1, for i = 1 to Q.

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 (Si × i) for all 1 ≤ i ≤ Q, where Si is the answer to the i-th question.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 4 × 105.
• 0 ≤ Ai < Mi, for all i.
• 0 ≤ Bi < Mi, for all i.
• 0 ≤ Ci < Mi, for all i.
• 0 ≤ X1 < M1.
• 0 ≤ X2 < M1.
• 0 ≤ Y1 < M2.
• 0 ≤ Y2 < M2.
• 0 ≤ Z1 < M3.
• 0 ≤ Z2 < M3.
• 1 ≤ Mi ≤ 109, for all i.