eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 10 секунд
Лимит использования памяти 64 MiB

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

d = |x_1 − x_2| + |y_1 − y_2|

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

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

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

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

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

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

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

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

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

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

Пример

Входные данные #1
4 3
ooxx
ooxx
ooxx
4 1
null
4 4
aabb
aabb
ccdd
ccdd
0 0
Выходные данные #1
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