#D30. Nice table
Nice table
Nice table
You are given an n × m table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every 2 × 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 ≤ n, m, n × m ≤ 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.
inputFormat
Input
First line contains two positive integers n and m — number of rows and columns in the table you are given (2 ≤ n, m, n × m ≤ 300 000). Then, n lines describing the table follow. Each line contains exactly m characters «A», «G», «C», «T».
outputFormat
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.
样例
3 5
AGCAG
AGCAG
AGCAG
AGCTC
CTAGA
AGCTC