Міста
Юний програміст вирішив придумати власну гру. Гра відбувається на полі розміром n × n клітинок, у деяких клітинках якого розміщено міста (кожне місто займає одну клітинку; у кожній клітинці може розміщуватись не більше одного міста). Усього повинно бути парна кількість міст.
Спочатку про кожну клітинку ігрового поля відомо, чи розміщено у ній місто чи ні. Щоб розпочати гру, необхідно розділити ігрове поле на дві держави так, щоб у кожній державі було порівну клітинок-міст.
Границя між державами повинна проходити по границям клітинок таким чином, щоб з довільної клітинки кожної держави існував шлях по клітинкам цієї ж держави у довільну іншу її клітинку (з клітинки можна перейти у сусідню, якщо вони мають спільну сторону). Кожна клітинка ігрового поля повинна належати лише одній з двох держав, при цьому держави не зобов'язані складатись з одинакової кількості клітинок.
Потрібно написати програму, яка з врхуванням сказаного розділить клітинки заданого ігрового поля між двома державами.
Вхідні дані
Перший рядок містить розмір ігрового поля n (1 ≤ n ≤ 50).
Наступні n рядків містять по n великих латинських букв (без пропусків), які кодують відповідні клітинки ігрового поля: C позначає клітинку, зайняту містом, D - порожню клітинку. Гарантується, що на полі є хоча б два міста і усього їх парне число.
Вихідні дані
Вивести n рядків по n цифр (без пропусків) у кожному, які кодують відповідні клітинки. Цифра 1 означає, що дана клітинка належить першій державі, цифра 2 - дана клітинка належить другій державі.
Якщо розв'язків декілька, необхідно вивести довільний з них.