O. Два государства

Игровое поле — квадрат $n \times n$. В некоторых клетках стоят города, всего городов чётное число и не меньше двух.

Поле нужно разделить на два государства так, чтобы городов в них было поровну и каждое государство было связным: из любой его клетки можно дойти до любой другой по клеткам того же государства, переходя между клетками с общей стороной. Каждая клетка достаётся ровно одному государству; по числу клеток государства могут различаться.

Чтобы ответ был единственным, разрез фиксирован. Обходим клетки змейкой: первую строку слева направо, вторую справа налево, третью снова слева направо и так далее. Первому государству должен достаться начальный кусок этого обхода, второму — всё остальное. Среди подходящих разрезов выведите тот, в котором первому государству досталось наименьшее число клеток.

Первая строка содержит число $n$ ($1 \le n \le 50$).

Следующие $n$ строк содержат по $n$ заглавных латинских букв: C — клетка с городом, D — пустая клетка.

Выведите $n$ строк по $n$ цифр: $1$ — клетка первого государства, $2$ — второго.