Watson and Intervals (Large)

Sherlock and Watson have mastered the C++ language in their programming course, so they have moved on to algorithmic problems. In today's class, the tutor introduced the problem of merging one-dimensional intervals. $N$ intervals are given, and the $i$-th interval is defined by the inclusive endpoints $[L_i, R_i]$, where $L_i \le R_i$.

The tutor defined the covered area of a set of intervals as the number of integers that appear in at least one of the intervals. Formally, an integer $p$ contributes to the covered area if there is some $j$ such that $L_j \le p \le R_j$.

Watson always likes to challenge Sherlock. This time he asked Sherlock to remove exactly one interval so that the covered area of the remaining intervals is as small as possible. Help Sherlock find this minimum possible covered area after removing exactly one of the $N$ intervals.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one test case.

Each test case is one line with eight integers $N$, $L_1$, $R_1$, $A$, $B$, $C_1$, $C_2$, and $M$. $N$ is the number of intervals, and the other seven values are parameters that you use to generate the remaining intervals, as follows.

First set $x_1 = L_1$ and $y_1 = R_1$. Then use the recurrences below to generate $x_i$ and $y_i$ for $i = 2$ to $N$:

• $x_i = (A \times x_{i-1} + B \times y_{i-1} + C_1) \bmod M$
• $y_i = (A \times y_{i-1} + B \times x_{i-1} + C_2) \bmod M$

For every $i$ from 2 to $N$, define $L_i = \min(x_i, y_i)$ and $R_i = \max(x_i, y_i)$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum possible covered area of all the intervals that remain after removing exactly one interval.

• $1 \le T \le 50$
• $0 \le L_1 \le R_1 \le 10^9$
• $0 \le A \le 10^9$
• $0 \le B \le 10^9$
• $0 \le C_1 \le 10^9$
• $0 \le C_2 \le 10^9$
• $1 \le M \le 10^9$
• $1 \le N \le 5 \times 10^5$ (500000)

In case 1, the generation method produces the single interval $[1, 1]$. Removing the only interval leaves a covered area of 0.

In case 2, the generated intervals are $[2, 5]$, $[3, 5]$, and $[4, 7]$. Removing the first, second, or third interval makes the covered area of the remaining intervals 5, 6, and 4, respectively.

In case 3, the generated intervals are $[3, 4]$, $[1, 9]$, $[0, 8]$, and $[2, 4]$. Removing the first, second, third, or fourth interval makes the covered area of the remaining intervals 10, 9, 9, and 10, respectively.