e-olymp
Задачи

Месть Вороного

Месть Вороного

Дискретная диаграмма Вороного является производной от диаграммы Вороного. Она представляется множеством точек. Каждая из образующих лежит в центре некоторой точки. Каждая точка относится к той образующей, расстояние по Манхетену до которой минимально. Манхетенским расстоянием d между двумя точками (x1, y1) и (x2, y2) вычисляется по формуле:

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

Вам следует найти множество образующих, которые генерируют заданную дискретную диаграмму Вороного. Каждая образующая задается в ней уникальной буквой нижнего регистра, являющейся ее идентификатором. Каждая точка задается идентификатором образующей, к которой она принадлежит. Если точка имеет несколько образующих, находящихся от нее на одинаковом расстоянии, то выбрать следует ту, которая имеет наименьший идентификатор (то есть наименьший символ).

Входные данные

Входные данные состоят из нескольких тестов.

Первая строка каждого теста содержит два целых числа W (1W32) и H (1H32) - ширину и высоту дискретной диаграммы Вороного.

Каждая из следующих H строк состоит из W букв, описывающих дискретную диаграмму Вороного. Каждая буква задает одну точку.

Последняя строка содержит два нуля и не обрабатывается.

Выходные данные

Для каждого теста вывести координаты образующих как показано в примере. Каждая строка, описывающая образующую, должна содержать ее идентификатор, а также x-координату и y-координату. Образующие следует выводить в алфавитном порядке их образующих. Координаты начинаются с нуля, (0, 0) является центром точки, находящейся в верхнем левом углу диаграмы.

Каждый тест имеет хотя бы одно решение. Если решений несколько, можно вывести любое.

После каждого теста следует выводить пустую строку, включая последний тест.

Лимит времени 10 секунд
Лимит использования памяти 64 MiB
Входные данные
4 3
ooxx
ooxx
ooxx
4 1
null
4 4
aabb
aabb
ccdd
ccdd
0 0
Выходные данные
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