Graduation Requirements (Large)

Students at Awesome Programmer University keep a tradition before they graduate. One part of it is driving around a traffic circle backwards. Going around once is reckless enough, so you want to go a step further and stay in the circle, driving backwards, as long as you can without stopping.

The traffic circle has $N$ intersections spaced evenly around it. A car enters the circle at one intersection, then moves to the next intersection counterclockwise every second, and leaves the circle when it reaches the intersection where it gets off.

You watched the traffic circle for $X$ seconds and recorded, for every car, the time it entered, the intersection it entered at, and the intersection it left at. Every car moves counterclockwise at one intersection per second. Every car you watched left the circle before coming back to the intersection it entered at. The circle has several lanes, so any number of cars may sit at the same intersection at the same time.

How many seconds could you have driven clockwise during that period? You enter the circle at an integer time of at least 0, you leave the circle at a time of at most $X$, and once you leave you cannot come back. Inside the circle you move clockwise at one intersection per second. You choose the time and the intersection where you enter, and the time when you leave.

Think of the circle as a continuous loop of length $N$, with you and every other car as points moving along that loop. At no instant, integer or not, may your point sit at the same place as the point of another car. So you cannot leave the circle at an intersection at the moment another car is entering there, you cannot enter the circle at an intersection at the moment another car is leaving there, and you cannot pass a car coming toward you, because the two of you would meet halfway between two intersections.

The first line has the number of test cases $T$. The first line of each test case has the number of observed cars $C$. The second line has two integers $X$ and $N$: the time in seconds for which you watched the circle, and the number of intersections on it. The $i$-th of the following $C$ lines has three integers $s_i$, $e_i$, $t_i$: the intersection where the car entered the circle, the intersection where it left, and the time at which it entered. Intersections are numbered from $1$ to $N$ counterclockwise, so intersection $2$ is the next intersection counterclockwise from intersection $1$.

Limits

• $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$
• Every observed car leaves the circle at time $X$ or earlier.

For each test case print one line in the form "Case #x: y", where x is the test case number starting from 1 and y is the largest number of seconds you can travel inside the circle. y is 0 both when you cannot enter the circle at all and when you can enter it but cannot move even one intersection.

You have to enter at an integer time, so you arrive at every intersection you pass at an integer time.

The first test case of the example input has one car, moving as in the picture above. There are several ways to drive backwards for one second. The other car is at intersection 1 at time 0, so you can enter at intersection 1 at time 1 and drive to intersection 4. Going on to intersection 3 would make you pass the car that moves from 3 to 4 during that second, so that is not allowed. You can also enter at intersection 4 at time 0 and drive to intersection 3.

In the second test case you drive for two seconds by entering at intersection 5 at time 1 and driving backwards to intersection 3. In the third test case you cannot even enter, because at every whole second there is a car at every intersection. The fourth test case has no cars, so you enter anywhere at time 0 and keep going until time 6. In the fifth test case you can enter, but the circle has only three intersections, so moving to the next one always collides with the other car.

Driving against traffic on a real traffic circle is dangerous. Do not try it.