codeforces#P1098B. Nice table

    ID: 29849 远端评测题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>brute forceconstructive algorithmsgreedymath*2100

Nice table

Description

You are given an n×mn \times m table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every 2×22 \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 nn and mm — number of rows and columns in the table you are given (2n,m,n×m3000002 \leq n, m, n \times m \leq 300\,000). Then, nn lines describing the table follow. Each line contains exactly mm characters «A», «G», «C», «T».

Output nn lines, mm 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 nn and mm — number of rows and columns in the table you are given (2n,m,n×m3000002 \leq n, m, n \times m \leq 300\,000). Then, nn lines describing the table follow. Each line contains exactly mm characters «A», «G», «C», «T».

Output

Output nn lines, mm characters each. This table must be nice and differ from the input table in the minimum number of characters.

Samples

输入数据 1

2 2
AG
CT

输出数据 1

AG
CT

输入数据 2

3 5
AGCAG
AGCAG
AGCAG

输出数据 2

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.