왓슨과 구간 (Large)

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

강사는 구간 집합의 덮인 넓이를 적어도 하나의 구간에 속하는 정수의 개수로 정의했다. 엄밀히 말하면, 어떤 $j$에 대해 $L_j \le p \le R_j$를 만족하는 정수 $p$가 덮인 넓이에 하나씩 더해진다.

왓슨은 늘 셜록에게 도전하기를 좋아한다. 이번에는 셜록에게 구간을 정확히 하나 제거해서 남은 구간의 덮인 넓이를 최소로 만들라고 했다. $N$개의 구간 중 정확히 하나를 제거했을 때 가능한 덮인 넓이의 최솟값을 구해 셜록을 도와주자.

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

각 테스트 케이스는 정수 8개 $N$, $L_1$, $R_1$, $A$, $B$, $C_1$, $C_2$, $M$으로 이루어진 한 줄이다. $N$은 구간의 개수이고 나머지 7개 값은 나머지 구간을 생성하는 매개변수로, 다음과 같이 사용한다.

먼저 $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$까지 모든 $i$에 대해 $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$
• $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)

1번 케이스에서 생성 방법에 따라 만들어지는 구간은 $[1, 1]$ 하나다. 유일한 구간을 제거하면 덮인 넓이는 0이다.

2번 케이스에서 만들어지는 구간은 $[2, 5]$, $[3, 5]$, $[4, 7]$이다. 첫 번째, 두 번째, 세 번째 구간을 제거하면 남은 구간의 덮인 넓이는 각각 5, 6, 4가 된다.

3번 케이스에서 만들어지는 구간은 $[3, 4]$, $[1, 9]$, $[0, 8]$, $[2, 4]$이다. 첫 번째, 두 번째, 세 번째, 네 번째 구간을 제거하면 남은 구간의 덮인 넓이는 각각 10, 9, 9, 10이 된다.