Revenge of Voronoi

Time Limit : 8 sec, Memory Limit : 65536 KB

Now judge is temporally not available for this problem. We are earnestly making necessary data. Sorry for the inconvenience.

Problem I: Revenge of Voronoi

A discrete Voronoi diagram is a derivation of a Voronoi diagram. It is represented as a set of pixels. Each of the generatrices lies on the center of some pixel. Each pixel belongs to the generatrix nearest from the center of the pixel in the sense of Manhattan distance. The Manhattan distance d between two points (x1, y1) and (x2, y2) is given by the following formula:

d = |x1 - x2| + |y1 - y2|

Your task is to find a set of generatrices which generates a given discrete Voronoi diagram. In the given diagram, each generatrix is given a unique lowercase letter as its identifier, and each pixel is represented by the identifier of the generatrix the pixel belongs to. If a pixel has multiple generatrices at the same distance from its center, it belongs to the generatrix with the most preceding identifier among them (i.e. the smallest character code).


The input consists of multiple test cases.

Each test case begins with a line containing two integers W (1 ≤ W ≤ 32) and H (1 ≤ H ≤ 32), which denote the width and height of the discrete Voronoi diagram.

The following H lines, each of which consists of W letters, give one discrete Voronoi diagram. Each letter represents one pixel.

The end of input is indicated by a line with two zeros. This is not a part of any test cases.


For each test case, print the case number and the coordinates of generatrices as shown in the sample output. Each generatrix line should consist of its identifier, x-coordinate, and y-coordinate. Generatrices should be printed in alphabetical order of the identifiers. Each coordinate is zero-based where (0, 0) indicates the center of the top-left corner pixel of the diagram.

You may assume that every test case has at least one solution. If there are multiple solutions, any one is acceptable.

Print a blank line after every test case including the last one.

Sample Input

4 3
4 1
4 4
0 0

Output for the Sample Input

Case 1:
o 0 0
x 2 0
Case 2:
l 2 0
n 0 0
u 1 0
Case 3:
a 0 0
b 2 0
c 0 2
d 2 2

Source: ACM-ICPC Japan Alumni Group Practice Contest , for World Finals, Tokyo, Japan, 2008-02-23