Юний програміст вирішив придумати власну гру. Гра відбувається на полі розміром n × n клітинок, у деяких клітинках якого розміщено міста (кожне місто займає одну клітинку; у кожній клітинці може розміщуватись не більше одного міста). Усього повинно бути парна кількість міст.

Спочатку про кожну клітинку ігрового поля відомо, чи розміщено у ній місто чи ні. Щоб розпочати гру, необхідно розділити ігрове поле на дві держави так, щоб у кожній державі було порівну клітинок-міст.

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

Потрібно написати програму, яка з врхуванням сказаного розділить клітинки заданого ігрового поля між двома державами.

Вхідні дані

Перший рядок містить розмір ігрового поля n (1 ≤ n ≤ 50).

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

Вихідні дані

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

Якщо розв'язків декілька, необхідно вивести довільний з них.