B. Nice table
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Examples
Input
2 2
AG
CT

Output
AG
CT

Input
3 5
AGCAG
AGCAG
AGCAG

Output
TGCAT
CATGC
TGCAT

Note

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