VORONOI - Revenge of Voronoi

no tags 

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).

Input

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.

Output

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.

Example

Input:
4 3
ooxx
ooxx
ooxx
4 1
null
4 4
aabb
aabb
ccdd
ccdd
0 0

Output:
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


hide comments
Tony Beta Lambda: 2010-06-29 08:00:24

I mistakenly deleted Lordxfastx's comment. The original text was:


The resource should be wintercamp 07 instead of 08.
BTW, have the testcases been modified?
Edited after AC: Oh no, there are 99 cases. Precalculation needs constant optimization.


Sorry for inconvenience.

Last edit: 2010-06-29 08:11:17
[Trichromatic] XilinX: 2009-09-24 12:08:27

Added some new test data :-)


Added by:Bin Jin
Date:2008-09-08
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:JAG wintercamp 08, day2