Limits 500ms, 512 MB

In a one dimensional world, a dragon called 'Google' is trying to reach its' destination. It starts from position 0 and wants to get to the end of the path. A path is defined with a series of '0' and '1'. '0' means that Google can go to that position and '1' means that there is an obstacle in that position, so Google can't go to that cell.

Google is very big. He can walk to the next position or jump to any valid next positions. Google can make a jump that has a length in the range of minJump and maxJump only. If Google makes a jump of length 'Y' from position 'X', his new position will be 'X+Y'.

Now given all the values, tell if Google can make it to the last position or not. See the sample input and output for more details.

Input

The first line will contain T, the number of test cases.
For every test case, one line will contain N: the length of the path; minJump: the minimum jump length, maxJump: the maximum jump length; The next line will contain N space-separated integers (0 or 1)
denoting the stage.

Constraints:
1 <= T < = 100;
1 <= N <= 10000;
1 <= minJump <= maxJump <= 10000 ;

Note : 95% of the test cases are generated randomly.

Output

For every test case, Print in this format, "Case X: Google Can!" or "Case X: Google Can Not!" where X is the case number.
Print "Google Can!" , when Google can reach the destination otherwise print "Google Can Not!" .

Sample

InputOutput
 4
 5 1 1
 0 0 0 0 0
 5 1 1
 0 1 0 1 0
 5 2 3
 1 1 1 1 1
 10 2 3
 0 1 1 0 1 1 0 1 1 0
Case 1: Google Can!
Case 2: Google Can Not!
Case 3: Google Can Not!
Case 4: Google Can!

Submit

Login to submit.

Statistics

31% Solution Ratio
spiritinchainsEarliest, Oct '19
nusuBotFastest, 0.0s
dip_BRURLightest, 131 kB
lelbabaShortest, 901B
Toph uses cookies. By continuing you agree to our Cookie Policy.