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

Секретный бункер

Секретный бункер

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

Имеется план секретного бункера в виде прямоугольного поля, на котором местоположение бомб отмечено символом '*', секретных объектов – символом '?', а пустые клетки – символом '.'. В случае опасности подрыв любой бомбы должен приводить к уничтожению секретных объектов. Бомба при взрыве уничтожает все объекты, для которых расстояние от центра клетки с бомбой до центра клетки с объектом меньше или равно D. Если в пределах действия бомбы оказывается другая бомба, она также взрывается.

Напишите программу, вычисляющую минимальное значение D, при котором взрыв любой бомбы приводит к уничтожению всех секретных объектов.

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

Во входном файле несколько тестов. В первом строке каждого теста содержатся два целых числа N и M через пробел – размеры плана бункера (1  ≤  N ≤  50, 1  ≤  M  ≤  50). Далее следует N строк, содержащих по M символов '.', '*' и '?'. План содержит от 1 до 100 символов '?' и от 1 до 100 символов '*'. Строка, содержащая "00", сигнализирует о завершении набора тестов и не обрабатывается.

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

В выходной файл для каждого теста вывести строку, содержащую одно вещественное число – минимальное значение D для соответствующего плана с точностью 10^{−6}.

Пример

Входные данные #1
2 3
*.*
.?.
5 5
***** 
.?.?.
..?..
.?.?.
*****
0 0
Выходные данные #1
1.414214
3.000000