23984번 - 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 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 ≤ x ≤ 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 × i) for all 1 ≤ i ≤ Q, where S_i 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:

• X₁ X₂ A₁ B₁ C₁ M₁
• Y₁ Y₂ A₂ B₂ C₂ M₂
• Z₁ Z₂ A₃ B₃ C₃ M₃

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

We define:

• X_i = (A₁ × X_{i - 1} + B₁ × X_{i - 2} + C₁) modulo M₁, for i = 3 to N.
• Y_i = (A₂ × Y_{i - 1} + B₂ × Y_{i - 2} + C₂) modulo M₂, for i = 3 to N.
• Z_i = (A₃ × Z_{i - 1} + B₃ × Z_{i - 2} + C₃) modulo M₃, 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.

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

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 4 × 10⁵.
• 0 ≤ A_i < M_i, for all i.
• 0 ≤ B_i < M_i, for all i.
• 0 ≤ C_i < M_i, for all i.
• 0 ≤ X₁ < M₁.
• 0 ≤ X₂ < M₁.
• 0 ≤ Y₁ < M₂.
• 0 ≤ Y₂ < M₂.
• 0 ≤ Z₁ < M₃.
• 0 ≤ Z₂ < M₃.
• 1 ≤ M_i ≤ 10⁹, for all i.

• Q = 1.

• 1 ≤ Q ≤ 10⁵.