Watson과 구간

Sherlock과 Watson은 프로그래밍 수업에서 C++ 언어의 복잡한 세부 사항을 완전히 익혔으므로, 이제 알고리즘 문제로 넘어갔다. 오늘 수업에서 강사는 일차원 구간을 병합하는 문제를 소개했다. N개의 구간이 주어지며, i번째 구간은 양 끝점을 포함하는 끝점 [$L_{i}$, $R_{i}$]로 정의된다. 여기서 $L_{i}$ ≤ $R_{i}$.

강사는 구간 집합의 덮인 영역을 적어도 하나의 구간에 나타나는 정수의 개수로 정의했다. (엄밀히 말해, $L_{j}$ ≤ p ≤ $R_{j}$를 만족하는 어떤 j가 존재하면 정수 p는 덮인 영역에 기여한다.)

Watson은 언제나 Sherlock에게 도전하기를 좋아한다. 그는 남은 구간들의 덮인 영역이 최소가 되도록 정확히 하나의 구간을 제거하라고 Sherlock에게 요청했다. N개의 구간 중 정확히 하나를 제거한 뒤 가능한 덮인 영역의 최솟값을 Help Sherlock 구한다.

제한

1 ≤ T ≤ 50. 메모리 제한: 1GB. 0 ≤ $L_{1}$ ≤ $R_{1}$ ≤ $10^{9}$. 0 ≤ A ≤ $10^{9}$. 0 ≤ B ≤ $10^{9}$. 0 ≤ $C_{1}$ ≤ $10^{9}$. 0 ≤ $C_{2}$ ≤ $10^{9}$. 1 ≤ M ≤ $10^{9}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ N ≤ 1000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 200초. 1 ≤ N ≤ 5 * $10^{5}$(500000).

각 테스트 케이스는 여덟 개의 정수 N, $L_{1}$, $R_{1}$, A, B, $C_{1}$, $C_{2}$, M이 있는 한 줄로 구성된다. N은 구간의 개수이며, 나머지 일곱 값은 다음과 같이 다른 구간들을 생성하는 데 사용해야 하는 매개변수이다.

먼저 x_{1} = $L_{1}$ 및 y_{1} = $R_{1}$로 정의한다. 그런 다음 아래의 점화식을 사용하여 i = 2부터 N까지 x_{i}, y_{i}를 생성한다.

• x_{i} = ( A*x_{i-1} + B*y_{i-1} + $C_{1}$ )을 M으로 나눈 나머지.

• y_{i} = ( A*y_{i-1} + B*x_{i-1} + $C_{2}$ )을 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에서 생성 방법을 사용해 생성된 구간의 집합은 다음과 같다. {$[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이 된다.