Tile Flipping (Easy)

Interview

Time limit1sMemory limit512 MB

Summary

Given the first row of an N by N black/white board, fill the remaining rows so that flipping every black tile once (which also flips its orthogonal neighbors) turns the whole board white.

Level: Medium6 of 10
Topics: Implementation, Simulation, Greedy, Matrix
Solved: No attempts yet

Problem

Jigui owns a curious game board. The board holds tiles in $N$ rows and $N$ columns, and every tile is black on one side and white on the other. Flipping one tile in place also flips the tiles orthogonally adjacent to it. Jigui likes to start from a board whose tiles are laid out at random and flip tiles until every tile shows its white side.

One day Jigui stepped away and a younger sibling found the board. The sibling did not know the rule of the game, so from the starting position the sibling simply flipped every tile that showed its black side, each one exactly once. To everyone's surprise, all tiles ended up showing their white side.

Jigui came back, and instead of explaining the rule decided to build a few more boards with the same property. Jigui is a skilled hacker and can ignore the flipping rule, flipping only the chosen tiles to reach any colour layout. Doing that with no restriction is dull, so Jigui leaves the tiles of the first row untouched and only decides the remaining tiles.

You are given the state of the first row. Find the board on which flipping every tile that shows its black side, each one exactly once, leaves all tiles showing their white side.

Input

The first line contains the board size $N$ ( $1 \le N \le 1000$ ).

The second line contains a string of length $N$ describing the first row of the board. The string consists only of # and ., where # is a tile fixed with its black side up and . is a tile fixed with its white side up.

Output

Print the completed board on $N$ lines. Write # for a tile showing its black side and . for a tile showing its white side. The first line must equal the string given in the input.

For every possible input the answer is guaranteed to exist and to be unique.

Examples3

Example 1
Input
```
3
.#.
```
Expected output
```
.#.
#.#
.#.
```
Example 2
Input
```
5
#..#.
```
Expected output
```
#..#.
.##.#
.###.
#.##.
.#..#
```

Example 3

Input

8
#.##.###

Expected output

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