B. Nice tabletime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputFirst 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».OutputOutput n lines, m characters each. This table must be nice and differ from the input table in the minimum number of characters.ExamplesInput
2 2
AG
CT
Output
AG
CT
Input
3 5
AGCAG
AGCAG
AGCAG
Output
TGCAT
CATGC
TGCAT
NoteIn the first sample, the table is already nice. In the second sample, you can change 9 elements to make the table nice.
2 2
AG
CT

AG CT 
['brute force', 'constructive algorithms', 'greedy', 'math', '*2100']