You are given an $n \times m$ table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every $2 \times 2$ square contains all four distinct characters. Your task is to find a nice table (also consisting of «A», «G», «C», «T»), that differs from the given table in the minimum number of characters.

Input

First line contains two positive integers $n$ and $m$ — number of rows and columns in the table you are given ($2 \leq n, m, n \times m \leq 300\,000$). Then, $n$ lines describing the table follow. Each line contains exactly $m$ characters «A», «G», «C», «T».

Output

Output $n$ lines, $m$ characters each. This table must be nice and differ from the input table in the minimum number of characters.

Note

In the first sample, the table is already nice. In the second sample, you can change 9 elements to make the table nice.