E. Поджог в лесу Берляндии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представим лес Берляндии как бесконечное клеточное поле. В каждой клетке растет дерево. Или росло, до недавних событий.

Разрушительный огонь бушевал в лесу и уничтожил несколько деревьев. У вас есть прямоугольная карта $$$n \times m$$$, которая описывает поврежденную часть леса. Сожженные деревья отмечены на карте как «X», в то время как остальные отмечены как «.». Вы можете быть уверены, что все поврежденные деревья отмечены на карте. Все деревья за пределами карты — не повреждены.

Пожарные быстро потушили огонь, и теперь расследуют данный инцидент. Основная версия — это поджог: в какой-то момент времени (примем этот момент за $$$0$$$) несколько деревьев были подожжены. В начале минуты $$$0$$$ горели только подожженные деревья. В конце каждой минуты огонь распространяется от горящего дерева к $$$8$$$ соседним к нему деревьям. В начале минуты $$$T$$$ огонь был потушен.

Пожарные хотят найти поджигателей так быстро как это возможно. Но проблема в том, что они не знают ни значение $$$T$$$ (как долго бушевал пожар), ни местоположение деревьев, которые были подожжены. Они хотят, чтобы вы определили максимальное значение $$$T$$$ (чтобы узнать, сколько времени в запасе у поджигателей) и возможное множество деревьев, которые были подожжены.

Заметим, что вы хотите максимизировать значение $$$T$$$, но множество деревьев может быть произвольным.

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

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^6$$$, $$$1 \le n \cdot m \le 10^6$$$) — размеры карты.

В следующих $$$n$$$ строках задана карта. Строка $$$i$$$ соответствует $$$i$$$-й строке карты и содержит строку из $$$m$$$ символов. $$$j$$$-й символ $$$i$$$-й строки либо «X», если соответствующее дерево сгорело, либо «.» — если осталось в целости.

Гарантируется, что карта содержит хотя бы один «X».

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

В первой строке выведите единственное число $$$T$$$ — максимальное время, которое мог гореть лес. В следующих $$$n$$$ строках выведите сертификат: карту (прямоугольник $$$n \times m$$$), на которой подожженные деревья отмечены как «X», а оставшиеся как «.».

Примеры
Входные данные
3 6
XXXXXX
XXXXXX
XXXXXX
Выходные данные
1
......
.X.XX.
......
Входные данные
10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........
Выходные данные
2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........
Входные данные
4 5
X....
..XXX
..XXX
..XXX
Выходные данные
0
X....
..XXX
..XXX
..XXX