Replace Crosses with Dots

You are given a grid of characters consisting of asterisks (*) and dots (.). A cross is defined by a central asterisk and four arms of equal length extending in the up, down, left, and right directions. Formally, for a cell at \( (i, j) \) to be the center of a cross of arm length \( L \) (with \( L \ge 1 \)), the following conditions must hold:

\[ \begin{aligned} \forall k \in \{1, 2, \dots, L\}: \quad &i - k \ge 0,\quad i + k < N,\quad j - k \ge 0,\quad j + k < M,\\ &grid[i-k][j] = grid[i+k][j] = grid[i][j-k] = grid[i][j+k] = '*'. \end{aligned} \]

Your task is to identify every cross in the grid and replace all asterisks belonging to any cross (i.e. the center and the arm cells) with dots. If a cell is part of multiple crosses, it will be replaced by a dot once detected. Note that crosses may overlap and removals should be performed in a way that larger crosses are removed before checking for smaller ones.

inputFormat

The first line of input contains two integers \( N \) and \( M \) separated by a space, representing the number of rows and columns of the grid respectively. The following \( N \) lines each contain a string of length \( M \), representing a row of the grid.

outputFormat

Output the modified grid in the same format: \( N \) lines each containing a string of length \( M \), where all crosses have been replaced by dots.

## sample

5 5
..*..
..*..
*****
..*..
..*..

.....
.....
.....
.....
.....

</p>