Кольорова таблиця

Задано таблицю $a$ розміру $n\times m$, що складається з символів «R», «G», «B».

Також задані цілі числа $c$ ($2\le c\le 3$) та $q$, де $c$ — це кількість різних символів, що можуть зустрічатись у таблиці. Якщо $c$ дорівнює $2$, то доступні лише символи «R» та «G»; якщо ж $c$ дорівнює $3$, то доступні символи «R», «G», «B».

Вам потрібно змінити значення не більше ніж $q$ елементів таблиці так, щоб не існувало пари сусідніх по стороні клітинок, які мають однакове значення. Зауважте, що якщо $c=2$, то забороняється використовувати символ «B» при зміні значень клітинок таблиці.

Гарантується, що при заданих обмеженнях існує спосіб змінити не більше ніж $q$ елементів таблиці так, щоб не існувало пари сусідніх по стороні клітинок, які мають однакове значення.

Зауважте, що в задачі немає блоку "без додаткових обмежень".

Вхідні дані

У першому рядку задано два цілі числа $n$ та $m$ ($1\le n,m\le 100$) — кількість рядків та стовпців таблиці $a$ відповідно.

У другому рядку задано два цілі числа $c$ ($2\le c\le 3$) та $q$, які позначають кількість доступних символів та кількість дозволених змін у таблиці відповідно.

У наступних $n$ рядках задано по $m$ символів — елементи таблиці $a$. Якщо $c=2$, то $a_{ij}\in$ «R», «G». Якщо $c=3$, то $a_{ij}\in$ «R», «G», «B».

Вихідні дані

Виведіть $n$ рядків по $m$ символів кожен, що описують таблицю після виконаних змін.

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

Приклади

Оцінювання

1. ($7$ балів): $n=1,c=3,q=\lfloor \frac{n\cdot m}{2}\rfloor$;

2. ($7$ балів): $n=1,c=2,q=\lfloor \frac{n\cdot m}{2}\rfloor$;

3. ($3$ бали): $c=3,q=n\cdot m$;

4. ($7$ балів): всі рядки таблиці $a$ однакові, $a[1][j]\ne a[1][j+1]$ (для $1\le j<m$), $c=3$, $q=\lfloor \frac{n\cdot m}{2}\rfloor$;

5. ($7$ балів): всі рядки таблиці $a$ однакові, $c=3$, $q=\lfloor \frac{n\cdot m}{2}\rfloor$;

6. ($13$ балів): $c=3,q=\lfloor \frac{2\cdot n\cdot m}{3}\rfloor$;

7. ($19$ балів): $c=3,n\le 5,m\le 100,q=\lfloor \frac{n\cdot m}{2}\rfloor$;

8. ($17$ балів): $c=2,q=\lfloor \frac{n\cdot m}{2}\rfloor$;

9. ($20$ балів): $c=3,q=\lfloor \frac{n\cdot m}{2}\rfloor$.