cho.sh

Tile Flipping (Hard)

Fill the free tiles so that flipping every black tile once leaves the whole board white, choosing the lexicographically smallest result or reporting impossibility.

Hard8MathGreedyBit manipulationImplementationNo attempts yetTime limit1sMemory limit512 MB

Problem

Jigui owns an unusual game board. The board carries tiles in N rows and N columns, and each tile is painted black on one side and white on the other. A tile can be flipped in place, and flipping one tile also flips the tiles next to it above, below, to the left and to the right. Jigui likes to take a board whose tiles are arranged at random and flip tiles until every tile shows its white side.

One day Jigui left the board for a moment, and Jigui's younger sibling found it. The sibling does not know the rule of the game, so the sibling simply took every tile that was showing its black side in the starting state and flipped each of them once. Surprisingly, every tile ended up showing its white side.

When Jigui came back, Jigui meant to explain the rule of the game, but wanted to watch the sibling enjoy it a little longer and decided to build a few more boards with the same property. Jigui is a great hacker, so Jigui can ignore the rule of the board and flip only the chosen tiles to produce any arrangement of colors. Flipping tiles with no condition at all is not much fun, so Jigui decided to leave some of the tiles on the board unflipped and build the arrangement with the rest.

Input

The first line contains the size of the board N (1 ≤ N ≤ 1000).

Each of the next N lines contains a string of N characters describing the state of the tiles. The string consists only of #, . and -. # is a tile fixed with its black side up, . is a tile fixed with its white side up, and - is a tile that Jigui can flip freely.

Output

Print, over N lines, a board on which flipping every tile that shows its black side exactly once leaves every tile showing its white side. As in the input, write # for a tile that shows its black side and . for a tile that shows its white side. A fixed tile must keep the color given in the input.

If several boards work, print the one whose string of N2N^2 characters, formed by reading the board from the first line to the last and each line from left to right, comes first in lexicographic order. Here . is taken to come before #.

If no board works, print thinking_face.