Представим лес Берляндии как бесконечное клеточное поле. В каждой клетке растет дерево. Или росло, до недавних событий.
Разрушительный огонь бушевал в лесу и уничтожил несколько деревьев. У вас есть прямоугольная карта \(n \times m\), которая описывает поврежденную часть леса. Сожженные деревья отмечены на карте как «X», в то время как остальные отмечены как «.». Вы можете быть уверены, что все поврежденные деревья отмечены на карте. Все деревья за пределами карты — не повреждены.
Пожарные быстро потушили огонь, и теперь расследуют данный инцидент. Основная версия — это поджог: в какой-то момент времени (примем этот момент за \(0\)) несколько деревьев были подожжены. В начале минуты \(0\) горели только подожженные деревья. В конце каждой минуты огонь распространяется от горящего дерева к \(8\) соседним к нему деревьям. В начале минуты \(T\) огонь был потушен.
Пожарные хотят найти поджигателей так быстро как это возможно. Но проблема в том, что они не знают ни значение \(T\) (как долго бушевал пожар), ни местоположение деревьев, которые были подожжены. Они хотят, чтобы вы определили максимальное значение \(T\) (чтобы узнать, сколько времени в запасе у поджигателей) и возможное множество деревьев, которые были подожжены.
Заметим, что вы хотите максимизировать значение \(T\), но множество деревьев может быть произвольным.
Выходные данные
В первой строке выведите единственное число \(T\) — максимальное время, которое мог гореть лес. В следующих \(n\) строках выведите сертификат: карту (прямоугольник \(n \times m\)), на которой подожженные деревья отмечены как «X», а оставшиеся как «.».