졸업 요건 (라지)

어썸 프로그래머 대학교 학생에게는 졸업을 앞두고 치르는 전통이 있다. 그중 하나가 회전교차로를 역주행으로 도는 것이다. 한 바퀴 도는 것만으로도 충분히 무모하지만, 너는 한 걸음 더 나아가 멈추지 않고 최대한 오래 역주행으로 버티고 싶다.

회전교차로에는 교차점 $N$개가 원을 따라 같은 간격으로 놓여 있다. 자동차는 교차점 하나에서 원에 진입한 다음 1초마다 반시계 방향으로 다음 교차점으로 이동하고, 빠져나갈 교차점에 도착하면 원을 떠난다.

너는 $X$초 동안 회전교차로를 지켜보면서 자동차마다 진입한 시각, 진입한 교차점, 빠져나간 교차점을 기록했다. 모든 자동차는 1초에 교차점 하나씩 반시계 방향으로 움직인다. 관찰한 자동차는 모두 진입한 교차점으로 되돌아오기 전에 원을 떠났다. 회전교차로에는 차선이 여러 개라서 같은 시각에 같은 교차점에 자동차가 여러 대 있어도 된다.

이 시간 동안 너는 시계 방향으로 최대 몇 초를 달릴 수 있을까? 0 이상의 정수 시각에 원에 진입하고 $X$ 이하의 시각에 원을 떠나야 하며, 한 번 떠나면 다시 들어올 수 없다. 원 안에서는 1초에 교차점 하나씩 시계 방향으로 움직인다. 진입 시각과 진입 교차점, 이탈 시각은 네가 고른다.

원을 길이 $N$의 연속된 고리로 보고 너와 다른 자동차를 그 고리 위를 움직이는 점이라고 하자. 정수 시각이든 아니든 어떤 순간에도 너의 점이 다른 자동차의 점과 같은 위치에 있으면 안 된다. 그래서 다른 자동차가 진입하는 순간에 그 교차점에서 원을 떠날 수 없고, 다른 자동차가 빠져나가는 순간에 그 교차점으로 진입할 수 없고, 마주 오는 자동차를 지나칠 수도 없다. 마주 보고 달리면 두 교차점 사이 한가운데에서 만나기 때문이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 관찰한 자동차의 수 $C$가 주어진다. 둘째 줄에는 정수 $X$와 $N$이 주어진다. $X$는 회전교차로를 지켜본 시간(초)이고, $N$은 교차점의 개수다. 이어지는 $C$개의 줄 가운데 $i$번째 줄에는 정수 $s_i$, $e_i$, $t_i$가 주어진다. 차례로 자동차가 진입한 교차점, 빠져나간 교차점, 진입한 시각이다. 교차점에는 반시계 방향으로 $1$번부터 $N$번까지 번호가 붙어 있다. 즉 $1$번에서 반시계 방향으로 다음 교차점이 $2$번이다.

제한

• $1 \le T \le 100$
• $0 \le C \le 1000$
• $1 \le X \le 10^{10}$
• $3 \le N \le 10^{10}$
• $1 \le s_i, e_i \le N$
• $s_i \ne e_i$
• $0 \le t_i$
• 관찰한 자동차는 모두 시각 $X$ 또는 그보다 이른 시각에 원을 떠난다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 회전교차로 안에서 달릴 수 있는 최대 시간(초)이다. 원에 아예 진입할 수 없을 때와, 진입은 할 수 있지만 다음 교차점으로 한 칸도 움직일 수 없을 때 모두 y는 0이다.

진입 시각은 정수여야 하므로 지나가는 모든 교차점에 정수 시각에 도착한다.

예제 입력의 첫 번째 테스트 케이스에는 자동차가 한 대 있고, 위 그림처럼 움직인다. 1초 동안 역주행하는 방법은 여러 가지다. 시각 0에는 다른 자동차가 1번 교차점에 있으므로, 시각 1에 1번 교차점으로 진입해서 4번 교차점까지 달릴 수 있다. 여기서 3번 교차점으로 더 가면 그 1초 동안 3번에서 4번으로 오는 자동차를 지나치게 되므로 안 된다. 시각 0에 4번 교차점으로 진입해서 3번 교차점까지 달리는 방법도 있다.

두 번째 테스트 케이스에서는 시각 1에 5번 교차점으로 진입해서 3번 교차점까지 역주행하면 2초를 달린다. 세 번째 테스트 케이스에서는 매 정수 시각마다 모든 교차점에 자동차가 있어서 진입조차 할 수 없다. 네 번째 테스트 케이스에는 자동차가 없으므로 시각 0에 아무 교차점으로 진입해서 시각 6까지 계속 돌면 된다. 다섯 번째 테스트 케이스에서는 진입은 할 수 있지만 교차점이 세 개뿐이라 다음 교차점으로 움직이면 반드시 다른 자동차와 부딪힌다.

실제 회전교차로에서 역주행하는 것은 위험하다. 따라 하지 않기를 권한다.