CF1098B Nice table

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.

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