졸업 요건

Awesome Programmer University을 졸업하기 전에, 학생들은 전통적으로 특정한 "졸업 요건"을 수행한다. 그중 하나는 회전 교차로를 역방향으로 주행하는 것이다. 대부분의 사람에게는 이것만으로도 충분히 무모하지만, 추가 도전으로 멈추지 않고 회전 교차로를 역방향으로 여러 바퀴 돌 수 있는지 알아보고자 한다.

회전 교차로는 원을 따라 균등한 간격으로 배치된 N개의 교차로로 이루어져 있다. 자동차는 보통 한 교차로에서 회전 교차로에 진입한 뒤, 최종적으로 목적지에 도착하여 빠져나갈 때까지 매초 다음 반시계 방향 교차로로 이동한다.

당신은 X초 동안 자동차들이 회전 교차로에 진입하고 빠져나가는 모습을 관찰했다. 각 자동차에 대해 회전 교차로에 진입한 시각과 진입 및 이탈한 교차로를 기록한다. 모든 자동차는 초당 1개의 교차로 속도로 반시계 방향으로 이동한다. 관찰한 각 자동차는 자신이 진입한 교차로로 되돌아오기 전에 회전 교차로에서 빠져나갔다. 회전 교차로에는 여러 차로가 있으므로 여러 자동차가 같은 시각에 같은 위치를 차지할 수 있다.

계획을 완벽하게 세웠다면, 이 시간 동안 회전 교차로에서 시계 방향으로 얼마나 오래 주행할 수 있었을까? 어떤 정수 시각 >= 0에 회전 교차로에 진입하고, 시각 <= X에 빠져나가야 하며, 한 번 빠져나간 뒤에는 다시 진입할 수 없다. 회전 교차로 안에서는 초당 1개의 교차로 속도로 시계 방향으로 이동해야 한다. 안전하게 행동하고 싶으므로(회전 교차로를 역방향으로 주행하면서 가능한 만큼은 안전하게), 다른 자동차와 접촉하거나 서로 스쳐 지나가서는 절대 안 된다. 특히 다른 자동차가 같은 순간에 진입하는 교차로에서 빠져나갈 수 없으며, 다른 자동차가 같은 순간에 빠져나가는 교차로에서 진입할 수도 없다. 회전 교차로에 진입하고 빠져나갈 시각과 장소는 선택할 수 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100 1 ≤ $s_{i}$, $e_{i}$ ≤ N $s_{i}$ ≠ $e_{i}$ 0 ≤ $t_{i}$ 관찰된 각 자동차는 시각 X 또는 그 이전에 회전 교차로에서 빠져나간다.

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

3 ≤ N ≤ 10 1 ≤ X ≤ 10 0 ≤ C ≤ 10

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

3 ≤ N ≤ $10^{10}$ 1 ≤ X ≤ $10^{10}$ 0 ≤ C ≤ 1000

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 관찰한 자동차의 수 C가 주어진다. 두 번째 줄에는 두 정수 X와 N이 주어진다. 이는 각각 회전 교차로를 관찰한 시간(초)과 회전 교차로에 있는 교차로의 수이다. 이어지는 C개의 줄에는 관찰한 자동차들이 주어진다. 각 줄에는 세 정수 $s_{i}$, $e_{i}$, $t_{i}$이 주어진다. 이는 각각 자동차가 회전 교차로에 진입한 교차로, 빠져나간 교차로, 진입한 시각이다. 교차로에는 반시계 방향으로 1부터 N까지 번호가 매겨져 있다(즉, 교차로 번호 2는 번호 1의 다음 반시계 방향 교차로이다).

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 회전 교차로에서 이동할 수 있는 최대 시간(초)이다. 회전 교차로에 전혀 진입할 수 없는 경우와 진입은 할 수 있지만 교차로 하나만큼도 이동할 수 없는 경우 모두 y가 영일 수 있음에 유의하라.

회전 교차로에는 정수 초로 표현되는 시각에 진입해야 한다는 점을 기억하라. 즉, 정수 시각에 진입해야 하며, 따라서 각 교차로에도 정수 시각에 도착한다.

첫 번째 예제 케이스에는 자동차가 하나 있으며, 문제 설명의 그림과 같이 이동한다. 우리가 역방향으로 일 초 동안 이동할 수 있는 방법은 여러 가지이다. 예를 들어 시각 1에 교차로 1에서 진입하여(다른 자동차가 그곳에 있으므로 시각 영에는 진입할 수 없다) 교차로 4까지 이동할 수 있다(다른 자동차가 3에서 4로 이동할 때 서로 스쳐 지나가게 되므로 교차로 3까지 계속 갈 수는 없다). 또 다른 방법은 시각 0에 교차로 4에서 진입하여 교차로 3까지 이동한 뒤 빠져나가는 것이다.

두 번째 예제 케이스에서는 시각 1에 교차로 5에서 진입하여 역방향으로 교차로 3까지 이동함으로써 이 초 동안 이동할 수 있다. 세 번째 예제 케이스에서는 회전 교차로에 진입조차 할 수 없다. 매 정수 초마다 모든 교차로에 자동차가 있기 때문이다. 네 번째 케이스에는 자동차가 없으므로 시각 0에 아무 지점에서나 회전 교차로에 진입하여 시각 6까지 계속 돌면 된다. 다섯 번째 케이스에서는 회전 교차로에 진입할 수 있지만, 교차로가 세 개뿐이므로 다음 교차로로 이동하려 하면 항상 다른 자동차와 충돌한다.

참고: 회전 교차로에서 교통 흐름의 반대 방향으로 운전하는 것은 일반적으로 현명한 행동이 아니며 자신이나 다른 사람에게 피해를 줄 수 있다. Google은(특히 Google Code Jam은) 이를 시도하지 말 것을 권고한다.