High School Programming League Problems Archive

You have just started playing a very interesting game. It consists of a rectangular grid in which each field contains a switch and is painted in one of the primary colors: red, green, or blue. Whenever you press a switch, not only its corresponding field, but the fields adjacent in the directions North, South, West, and East change their colors according to the following rules:

• Red changes to green.
• Green changes to blue.
• Blue changes to red.

The goal of the game is to make the whole grid red. You are to write a program that reaches the goal using as few switch presses as possible.

Input

Input starts with an integer (1 <= T <= 100), the number of test cases. T test cases follow, each describing a particular state of the game in the following manner: two space separated integers (1 <= R, C <= 50) the number of rows and columns of the grid, respectively. R lines of length C follow, each describing a row of the grid and consisting only of uppercase characters 'R', 'G', and 'B'.

Output

The first line of output for the i-th test case must consist of the word 'Case', a space, the integer i, a colon, a space and one of the characters 'Y' or 'N' depending on your choice to solve the i-th test case or not. Iff your choice was 'Y' then print two space separated integers (P, S) on the following line, representing the number of switch presses used to reach the goal and the number of switches pressed at least once. S lines must follow, each consisting of three space separated integers (R, C, P) representing the location of the switch (zero-indexed row and column) and the number of presses for that switch. Each switch must either appear never or just once in the same test case.

Scoring

You will get max(0, 3RC - P) for a correctly solved test and 0 points for unsolved tests. The total score of your program is the sum of scores obtained for individual devices.

The number of points displayed in the ranking is scaled so that it is equal to 10 for the contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
2
3 3
RGR
GBG
RGR
4 3
RGR
GBG
GBG
RGR

Output:
Case 1: N
Case 2: Y
4 2
1 1 2
2 1 2

Scoring:
32

Notes

• For the first four weeks of the series (till noon Saturday, January 9) all submissions to this problem will be visible to all users and tested on 5 data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on all 10 data sets. (Earlier solutions will also be extended to all 10 data sets.)