All Submissions

The Suvernarekha river once had a bridge of stones like the one below...

But now this bridge made of stones is not in good condition. The river has N stones forming the bridge and the the width of the river is D. The stones have been classified into two types, namely Stable(S) and Unstable(U). Unstable stones are those which can be used only once for crossing. When you first jump on an Unstable stone, it remains afloat. But as soon as you leave the stone, it sinks. Stable stone always remains afloat. So they can be used again and again.

You get up on an early morning to admire the sunrise at BIT and go to the river. Very soon after witnessing the sunrise, you get bored. You see the stone bridge and want to do something adventurous. You want to cross the river, say hi to the villagers on the other side and come back. Now that the bridge is not in a proper condition, making it to the other side and coming back is a challenging task. You see, estimate and analyse what should be the longest jump you'll have to make. Obviously, you will want to minimize the length of the longest jump.

Input Specification
The first line contains a integer T, denoting the number of test cases followed a blank line.
Each test case begins with a line containing two integers N and D. This is followed by the description of N stones in the next line. Description has a character U or S, depending on the type of stone and an integer which tells the position (di) of the ith stone from the side of the river you are standing on. Each test case is followed by a blank line.

Output Specification
Display one line for each test case in the format shown in sample. You have to print the test case number and the length of the longest jump you will have to make.

Sample Input

1 10
S 5

1 10
U 5

2 10
S 3 U 6

10 91
S 21 U 39 S 39 U 59 S 61 U 75 U 78 U 79 S 87 U 88

Sample Output
Case 1: 5
Case 2: 10
Case 3: 7
Case 4: 22

1 <= T <= 100
0 <= N <= 104
1 <= D <= 109
0 < di < D

Problem Setter : Shikhar Sharad

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes


Login to post clarification.

No Clarifications.


Mode Judge



Overall Rankings