Юный программист решил придумать собственную игру. Игра происходит на поле размером n × n клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.

Граница между государствами должна проходить по границам клеток таким образом, чтобы из любой клетки каждого государства существовал путь по клеткам этого же государства в любую другую его клетку (из клетки можно перейти в соседнюю, если они имеют общую сторону). Каждая клетка игрового поля должна принадлежать только одному из двух государств, при этом государства не обязаны состоять из одинакового количества клеток.

Напишите программу, которая разделит клетки заданного игрового поля между двумя государствами.

Входные данные

Первая строка содержит размер игрового поля n (1 ≤ n ≤ 50).

Последующие n строк содержат по n заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: C обозначает клетку, занятую городом, D - пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их чётное число.

Выходные данные

Вывести n строк по n цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 - данная клетка принадлежит второму государству.

Если решений несколько, необходимо вывести любое из них.