You're play a modified version of Conway's Game of Life on a 2D grid. Each cell on the grid can be represented as three states:
An asterisk, representing a cell that is "alive"
A period, representing a cell that is "dead"
An uppercase X, representing a "barrier".
On each turn, cells change their state depending on the following rules:
1. If the cell is not a barrier and is adjacent to any dead cells, the cell becomes a dead cell
2. If the cell is a barrier, is adjacent to only barriers, and is not on the edge of the board, it becomes a dead cell
Note that in these definitions, "adjacent to" refers to all 8 of the spaces next to a cell, including diagonally. Also note that all of the changes to cells take effect after the current turn, so the order that you apply the operations in doesn't matter.
It can be shown that if played infinitely many times, this (simplified) version of Conway's Game of Life will eventually converge on a single board state, i.e. the board will eventually never change between turns. Given a starting board, figure out the final state of the board if played infinitely many times.
The first line of input contains two positive integers $n$ and $m$: the number of rows and columns, respectively. The next $n$ lines each contain $m$ characters, each representing a cell of the board, according to the rules above.
Output a $n$ by $m$ board in the same format as the input: the final state of the board, after running the algorithm infinitely many times.
## Input
The first line of input contains two positive integers $n$ and $m$: the number of rows and columns, respectively. The next $n$ lines each contain $m$ characters, each representing a cell of the board, according to the rules above.
## Output
Output a $n$ by $m$ board in the same format as the input: the final state of the board, after running the algorithm infinitely many times.
[samples]
**Definitions**
Let $ G = (V, E) $ be a grid graph with $ n $ rows and $ m $ columns, where each cell $ v_{i,j} \in \{ '*', '.', 'X' \} $ for $ i \in \{1, \dots, n\}, j \in \{1, \dots, m\} $.
Let $ N(v_{i,j}) $ denote the set of 8 Moore neighbors of cell $ v_{i,j} $.
**Rules**
For each cell $ v_{i,j} $, its next state $ v_{i,j}' $ is determined as follows:
1. If $ v_{i,j} \neq 'X' $ and $ \exists \, u \in N(v_{i,j}) $ such that $ u = '.' $, then $ v_{i,j}' = '.' $.
2. If $ v_{i,j} = 'X' $ and $ \forall \, u \in N(v_{i,j}), u = 'X' $, and $ v_{i,j} $ is not on the boundary of the grid (i.e., $ 2 \leq i \leq n-1 $ and $ 2 \leq j \leq m-1 $), then $ v_{i,j}' = '.' $.
3. Otherwise, $ v_{i,j}' = v_{i,j} $.
**Constraints**
- $ n, m \in \mathbb{Z}^+ $, $ 1 \leq n, m \leq \text{some upper bound (implicit)} $
- Initial state: $ v_{i,j} \in \{ '*', '.', 'X' \} $ for all $ i,j $
**Objective**
Compute the fixed point of the update rule applied iteratively until convergence:
Find $ G^* = \lim_{t \to \infty} G^{(t)} $, where $ G^{(t)} $ is the state after $ t $ updates, and $ G^{(t+1)} $ is obtained by applying the above rules synchronously to all cells of $ G^{(t)} $.
Output $ G^* $ as an $ n \times m $ grid of characters.