题目描述
We are well known with the two personalities Gabbar Singh & Phoolan Devi. Gabbar Singh , the most iconic villain of Hindi Film Industry whereas Phoolan Devi , the Bandit Queen.
Now the battle is in between these two for expanding their territory. The dual came face to face for fighting for their territory.
But this time its not the Battle with guns or grenade , instead they both chosen a peaceful method for solving their hunger for territory.
A race was held between them , and the one who reach exactly on the Finishing Line first will win. If the both reach exactly on the Finishing Line at same time its a Tie. And for any other condition the race will be counted as Invalid.
Now during the race they both speed up and slow down frequently. Each time any of them Speed Up it increase their s[peed by one unit. And for Slowing Down condition it will decrease the Speed with a factor of one unit.
At start their position are at zero and their speed is also equal to zero
Find out the result of race
Input : First line will contain an integer T number of Test Cases. Each test case will contain the following inputs . First line of each test case will tell the integer L length of Race Track. Second line of each test case will tell integer C the number of changes in their speeds . Then next C lines will have G F characters. Please see the property for character G F
if G/F => F , it means Speed Up
if G/F => B , it means Slow Down
if G/F => W , nothing
Output : Print the result. If Gabbar Singh wins then print GABBAR SINGH , if Phooaln Devi wins print PHOOLAN DEVI , if its a tie then print TIE , if race is invalid then print INVALID. For each test case print result in new line.
Format of output is Case x: y where x is test case number and y is result
Constraints
1 ≤ T ≤ 100
15 ≤ L ≤ 10^6
1 ≤ C ≤ 100
UPDATE : For the given problem both Gabbar Singh and Phoolan Devi starts with zero position. Length of track is given and race is organised. Till the completion of race speed of both are changed which can be fetched from the corresponding inputs. 'F' means increment of one in speed , 'B' means decrements of one in speed, 'W' means no change in speed.
Now one who reached exactly on Finishing Line of track first will win. Note that , position change from current Position depends on current speed of them.
SAMPLE INPUT
2
25
6
F F
B B
W W
F F
B F
W F
15
8
F F
F W
F F
F F
B F
B B
F F
F B
SAMPLE OUTPUT
Case 1: PHOOLAN DEVI
Case 2: GABBAR SINGH
Explanation
In Case 1 : Phoolan Devi will reach first exactly on Finishing Line
In Case 2 : Gabbar Singh will reach first exactly on Finishing Line
输入格式
见题面
输出格式
见题面