Cities

A young programmer decided to invent a game of his own. The game takes place on an N × N board of cells, some of which contain cities. Each city occupies one cell, and no cell contains more than one city. The total number of cities must be even.

Initially, whether each cell of the board contains a city is known. To start the game, the board must be divided into two states so that each state contains the same number of city cells.

The border between the states must run along cell borders, and from any cell of a state there must be a path to any other cell of that state that passes only through cells of the same state. Two cells can be traversed between each other if they share a side. Every cell of the board must belong to exactly one of the two states, and the states do not have to contain the same number of cells.

Write a program that divides the cells of the given board between two states as described.

The first line of the input contains a single positive integer N, the size of the board (1 ≤ N ≤ 50).

The next N lines each contain N uppercase Latin letters with no spaces, encoding the corresponding cells of the board: 'C' denotes a cell occupied by a city, 'D' denotes an empty cell. The board is guaranteed to contain at least two cities, and their total number is even.

The output must contain N lines of N digits each, with no spaces, encoding the corresponding cells. The digit 1 means the cell belongs to the first state, and the digit 2 means the cell belongs to the second state.

If there are several solutions, output any one of them.