Вам надається сітка ~n \times m~, де кожна клітинка містить один символ A, B, C або D.

Для кожної клітинки ви повинні змінити символ на A, B, C або D. Новий символ має відрізнятися від старого.

Ваше завдання полягає в тому, щоб змінити символи в кожній клітинці таким чином, щоб жодні дві сусідні клітинки не мали однакового символу.

Обмеження

• ~1 \le n, m \le 500~

Формат вхідних даних

У першому рядку два цілі числа ~n~ і ~m~: кількість рядків і стовпців.

Наступні ~n~ рядків містять по ~m~ символів: опис сітки.

Формат вихідних даних

Вивести ~n~ рядків по ~m~ символів у кожному: опис кінцевої сітки.

Ви можете роздрукувати будь-яке дійсне рішення.

Якщо рішення не існує, просто надрукуйте IMPOSSIBLE.

Приклад вхідних даних

3 4
АААА
BBBB
CCDD

Приклад вихідних даних

CDCD
DCDC
ABAB