C. И снова лабиринт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карта уровня некоторой игры представляет собой прямоугольный лабиринт размером $$$N \times M$$$ клеток. Игроку нужно пройти из левой верхней клетки в правую нижнюю. За один шаг можно сдвинуться на соседнюю по стороне клетку, если в ней нет препятствия.

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

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

В первой строке записаны два числа $$$N$$$ и $$$M$$$ ($$$1 \le N, M \le 1000$$$).

Далее идет $$$N$$$ строк по $$$M$$$ символов, обозначающих клетки лабиринта: символ '.', если клетка свободна, и символ 'X', если занята.

Гарантируется, что верхняя левая и нижняя правая клетки свободны и между ними существует путь.

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

Выведите карту лабиринта (размеры выводить не надо), отметив символом '*' те клетки, в которые можно поставить дополнительное препятствие.

Пример
Входные данные
4 5
.....
.XX..
.X...
...X.
Выходные данные
.***.
.XX..
.X...
...X.