왓슨과 구간 (스몰)

셜록과 왓슨은 프로그래밍 수업에서 C++을 충분히 익히고 알고리즘 문제로 넘어갔다. 오늘 수업에서 조교는 일차원 구간을 합치는 문제를 소개했다. 구간 $N$개가 주어지고, $i$번째 구간은 양 끝을 포함하는 $[L_i, R_i]$로 정의된다. 여기서 $L_i \le R_i$이다.

조교는 구간 집합의 덮인 넓이를 적어도 한 구간에 속하는 정수의 개수로 정의했다. 정확히 말하면, $L_j \le p \le R_j$인 $j$가 존재할 때 정수 $p$가 덮인 넓이에 기여한다.

왓슨은 늘 셜록에게 도전 과제를 낸다. 이번에는 구간을 정확히 하나 지워서 남은 구간의 덮인 넓이를 가장 작게 만들라고 했다. 구간 $N$개 중 정확히 하나를 지운 뒤 얻을 수 있는 덮인 넓이의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 정수 여덟 개 $N$, $L_1$, $R_1$, $A$, $B$, $C_1$, $C_2$, $M$이 공백으로 구분되어 한 줄에 주어진다. $N$은 구간의 개수이고, 첫 번째 구간은 $[L_1, R_1]$이다. 나머지 일곱 값은 남은 구간을 만드는 데 쓰는 파라미터다.

먼저 $x_1 = L_1$, $y_1 = R_1$로 둔다. 그다음 $i = 2$부터 $N$까지 아래 점화식으로 $x_i$와 $y_i$를 생성한다.

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

$i = 2$부터 $N$까지 $L_i = \min(x_i, y_i)$, $R_i = \max(x_i, y_i)$로 정한다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 구간을 정확히 하나 지운 뒤 남은 구간의 덮인 넓이의 최솟값이다.

• $1 \le T \le 50$
• $1 \le N \le 1000$
• $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, 1]\}$ 하나뿐이다. 하나뿐인 구간을 지우면 덮인 넓이는 $0$이다.

두 번째 케이스에서 생성된 구간은 $\{[2, 5], [3, 5], [4, 7]\}$이다. 첫 번째, 두 번째, 세 번째 구간을 각각 지우면 남은 구간의 덮인 넓이는 차례로 $5$, $6$, $4$가 된다.

세 번째 케이스에서 생성된 구간은 $\{[3, 4], [1, 9], [0, 8], [2, 4]\}$이다. 첫 번째부터 네 번째까지 구간을 각각 지우면 남은 구간의 덮인 넓이는 차례로 $10$, $9$, $9$, $10$이 된다.