Junior programmer decided to invent his own game. The game takes place on the grid of size n × n cells. In some cells the cities are located (Each city occupies a single cell; in each cell may be located no more than one city). There should be an even number of cities.

Initially it is known about every cell of the playing field, is there a city or not. To start the game, you need to divide the grid into two states so that each state has equal number of city cells.

The boundary between the states should be held along the cells so that from each cell of any state there were a way to any other cell of the same state (from the cell one can go to another only if cells have common side). Each cell of the playing field should belong to only one of two states. It is not necessarily for the states to consist of the same number of cells.

Write a program that will divide the cells of the playing field between two countries.

Input

First line contains the size of playing field n (1 ≤ n ≤ 50).

Each of the next n lines contains n capital Latin letters (without spaces), coding for the corresponding cells of the playing field: C means the cell with city, D means empty cell. It is guaranteed that the field has at least two cities and their total number is even.

Output

Print n lines with n digits (without spaces) in each, coding for the corresponding cells. Digit 1 indicates that the cell belongs to the first state, digit 2 indicates that the cell belongs to the second state.

If multiple solutions exist, print any of them.