Grid Coloring I

You are given an $n\times mn\backslash times\; m$ grid where each cell contains one character A, B, C or D.

For each cell, you must change the character to A, B, C or D. The new character must be different from the old one.

Your task is to change the characters in every cell such that no two adjacent cells have the same character.

Input

The first line has two integers $nn$ and $mm$: the number of rows and columns.

The next $nn$ lines each have $mm$ characters: the description of the grid.

Output

Print $nn$ lines each with $mm$ characters: the description of the final grid.

You may print any valid solution.

If no solution exists, just print IMPOSSIBLE.