28856번 - Башни 스페셜 저지다국어

Ричмонд Валентайн построил башни сотовой связи, через которые он планирует передавать сигнал на SIM-карты его компании. Теперь он хочет найти территорию, которую покрывают его башни.

Карта Земли представляет собой клетчатую таблицу $n$ на $m$. Башни занимают ровно одну клетку в этой таблице. Назовём фигуру из клеток связной, если из каждой клетки этой фигуры можно дойти до всех остальных, идя только через границу клеток и проходя только по клеткам этой фигуры. Назовём связную фигуру клеточно-выпуклой, если для каждой вертикальной и горизонтальной прямой, фигура пересекает эту прямую в не более чем одном непрерывном отрезке. Тогда Ричмонд Валентайн считает, что башни покрывают минимальную связную клеточно-выпуклую фигуру, которая содержит все построенные им башни. Теперь он хочет найти область, которую покрывают его башни.

В первой строке входного файла находится целые числа $n$ и $m$ --- размеры Земли ($1 \le n, m \le 500$). В следующих $n$ строчек по $m$ символов находится описании карты Земли. Если в клетки ($i$, $j$) находится башня, то $j$-й символ $i$-й строки равен <<\t *>>, иначе этот символ равен <<\t .>>.

Выведите $n$ строк по $m$ символов в каждой. Если клетка ($i$, $j$) лежит в покрытой области, то $j$-й символ $i$-й строки должен быть равен <<\t *>>, иначе он должен быть равен <<\t .>>.

Если ответов несколько, выведите любой.