Problem Description

For an integer $2 \leq N \leq 50$, there is a grid with $N$ rows and $2N - 1$ columns.

The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $(i, j)$.

This grid is painted in black and white in a mountain shape. Specifically, for $1 \leq i \leq N$ and $1 \leq j \leq (2N - 1)$ satisfying $|j - N| < i$, cell $(i, j)$ is painted black, and the other cells are painted white.

Below is an example for $N = 5$ (# represents a black cell and . represents a white cell):

....#....
...###...
..#####..
.#######.
#########

Some of the black cells are then marked with X.

The state after marking is given as a $N \times (2N - 1)$ 2D array of characters $S$, where $S_{i, j}$ represents the state of cell $(i, j)$. If $S_{i, j}$ is X, cell $(i, j)$ is a black cell marked with X; if $S_{i, j}$ is #, cell $(i, j)$ is a black cell not marked with X; if $S_{i, j}$ is ., cell $(i, j)$ is a white cell.

Then, for $i = N - 1, N - 2, \cdots, 1$, perform the following operation:

• For $2 \leq j \leq 2N - 2$, if cell $(i, j)$ is black but not marked with X, and at least one of the cells $(i+1, j-1), (i+1, j), (i+1, j+1)$ is marked with X, mark cell $(i, j)$ with X.

Calculate the state of the grid after all operations are completed.

Input Format

The input is given from the standard input in the following format:

$N$ $S_{1,1}S_{1,2}\cdots S_{1,2N-1}$ $S_{2,1}S_{2,2}\cdots S_{2,2N-1}$ $:$ $S_{N,1}S_{N,2}\cdots S_{N,2N-1}$

Output Format

Output the state of cell $(i, j)$ after all operations as $T_{i,j}$ (X if black and marked with X, # if black and not marked with X, . if white) in the following format:

$T_{1,1}T_{1,2}\cdots T_{1,2N-1}$ $T_{2,1}T_{2,2}\cdots T_{2,2N-1}$ $:$ $T_{N,1}T_{N,2}\cdots T_{N,2N-1}$

Sample Input and Output

Sample Input #1

5
....#....
...##X...
..#####..
.#X#####.
#########

Sample Output #1

....X....
...XXX...
..XX###..
.#X#####.
#########

Sample Input #2

2
.#.
#X#

Sample Output #2

.X.
#X#

Sample Input #3

10
.........#.........
........###........
.......#####.......
......#######......
.....#########.....
....###########....
...#############...
..###############..
.#################.
X#X########X#X####X

Sample Output #3

.........X.........
........XXX........
.......XXXXX.......
......XXXXXXX......
.....XXXXXXXXX.....
....XXXXXXXXXXX....
...XXX##XXXXXXXX...
..XXX####XXXXXXXX..
.XXX######XXXXX##X.
X#X########X#X####X

Notes/Hints

Note

Discussion of this problem is prohibited until May 2, 2020, 18:00 JST. Disclosure of information may lead to claims for damages.

It is acceptable to publish the total score and certification level after the exam, but please refrain from disseminating information about which problems were solved.

Constraints

• $2 \leq N \leq 50$
• $S_{i, j}$ is either ., #, or X
• The state of the grid corresponding to $S$ can be obtained by marking at least one of the black cells with X in a mountain-shaped grid.

见题面 Input 部分

见题面 Output 部分