Nice table
Description
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.
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 $n$ lines, $m$ characters each. This table must be nice and differ from the input 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.
Samples
2 2
AG
CT
AG
CT
3 5
AGCAG
AGCAG
AGCAG
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.