Problem Description

Tomoaki, who is studying the history of the Tenkaichi Kingdom, is researching HAGIXILE, a great hero who led the kingdom.

HAGIXILE was known for his eccentric behavior. He divided the kingdom's territory into a grid of $N \times N$ squares, treating them as either white or black squares.

White squares represented regions he would visit that year, while black squares represented regions he would not visit.

The colors of the squares changed annually based on the colors of the squares from the previous year's grid.

If the number of black squares adjacent to a given square (up, down, left, right) was even, the square would become white after the recoloring; if odd, it would become black.

Corner squares have 2 adjacent squares, edge squares (excluding corners) have 3 adjacent squares, and non-edge squares have 4 adjacent squares.

For example, if white squares are represented by $ . $ and black squares by $ # $, and the grid for a certain year is as follows:

.#.
.##
.#.

The following year, it would be recolored as:

##.
###
##.

Tomoaki found the oldest known grid in a historical book and came up with the idea of restoring the grid before the recoloring.

Given the oldest grid, output one possible grid before the recoloring. Note that there is always at least one such grid before the recoloring.

Input Format

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

$ N $ $ C1,1C1,2..C1,N $ $ C2,1C2,2..C2,N $ : $ CN,1CN,2..CN,N $

• The first line contains an integer $N\ (1 \leq N \leq 750)$, representing the number of columns and rows.
• The next $ N $ lines contain the color $Ci,j\ (1 \leq i, j \leq N)$ of the square at row $ i $ and column $ j $.
• White squares are represented by $ . $ and black squares by $ # $.
• The given grid always has at least one possible grid before the recoloring.

Output Format

Output the colors before the recoloring in $ N $ lines, each containing $ N $ characters. End each line with a newline character.

Sample Input and Output

Sample Input #1

3
##.
###
##.

Sample Output #1

.#.
.##
.#.

Sample Input #2

5
.....
.....
.....
....#
...#.

Sample Output #2

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

Sample Input #3

10
#...#.#.#.
.####.#..#
##..###..#
#...###...
.#.#.##...
..##.##..#
######..#.
.#.....#..
.#...#####
..##...###

Sample Output #3

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

Notes/Hints

Partial Points

• Correct solutions for cases where $1 \leq N \leq 3$ will award 25 points as partial credit.
• Correct solutions for cases where $1 \leq N \leq 9$ will award an additional 30 points as partial credit.

Sample Explanation 1

For the square at row 1, column 1 of the output grid, there is no square above or to the left. The square to the right is $ # $ and below is $ . $. The number of black squares adjacent to it is 1, which is odd, so the color after recoloring is $ # $. Similarly, for the square at row 1, column 2, there is no square above, the left square is $ . $, the below square is $ # $, and the right square is $ . $. The number of black squares adjacent to it is 1, which is odd, so the color after recoloring is $ # $. Likewise, for the square at row 1, column 3, there is no square above, the left square is $ # $, the below square is $ # $, and there is no square to the right. The number of black squares adjacent to it is 2, which is even, so the color after recoloring is $ . $. Performing this recoloring for all squares matches the input grid, making it a correct solution.

见题面 Input 部分

见题面 Output 部分