1098_B. 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.
```python
from itertools import permutations
from sys import stdin, stdout
ly, lx = map(int, input().split())
grid = [[c for c in inp] for inp in stdin.read().splitlines()]

first = set()
bl = []
bpattern = []
bcost = 1e6
flip_row = False

for l in permutations('AGCT'):
    if bcost == 0:
        break
    if ''.join(l[:2]) in first:
        continue

    first |= set([''.join(l[:2]), ''.join(l[1::-1])])
    #try row flip
    cost = 0
    pattern = [0] * ly
    for i in range(ly):
        diff1, diff2 = 0, 0
        for j in range(lx):
            if grid[i][j] != l[((i & 1) << 1) + (j & 1)]:
                diff1 += 1
            if grid[i][j] != l[((i & 1) << 1) + ((j ^ 1) & 1)]:
                diff2 += 1
        cost += min(diff1, diff2)
        if diff1 >= diff2:  # 1 -> diff1, 0 -> diff2
            pattern[i] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = True
        bl = l
    # try col flip
    cost = 0
    pattern = [0] * lx
    for j in range(lx):
        diff1 = diff2 = 0
        for i in range(ly):
            if grid[i][j] != l[((j & 1) << 1) + (i & 1)]:
                diff1 += 1
            if grid[i][j] != l[((j & 1) << 1) + ((i ^ 1) & 1)]:
                diff2 += 1
        cost += min(diff1, diff2)
        if diff1 >= diff2:
            pattern[j] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = False
        bl = l

if flip_row:
    for i in range(ly):
        grid[i] = ''.join(
            [bl[((i & 1) << 1) + ((j ^ bpattern[i]) & 1)] for j in range(lx)])

else:
    for i in range(ly):
        grid[i] = ''.join(
            [bl[((j & 1) << 1) + ((i ^ bpattern[j]) & 1)] for j in range(lx)])

# print(f'need at least:{bcost}')
print('\n'.join(''.join((k for k in grid[i])) for i in range(ly)))
```