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.
In the first sample, the table is already nice. In the second sample, you can change 9 elements to make the table nice.
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.
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v
(n, m) = map(int, input().split())
u = list('AGCT')
d = dict()
for i in range(4):
    d[u[i]] = i
s = [0] * (n * m)
for i in range(n):
    s0 = list(input().rstrip().decode())
    for j in range(m):
        s[f(i, j)] = d[s0[j]]
(ma1, m1, m2) = (-1, [], [])
for i in range(4):
    for j in range(i + 1, 4):
        (c1, c2) = ([i, j], [])
        for k in range(4):
            if i ^ k and j ^ k:
                c2.append(k)
        c = 0
        for k in range(n):
            (a, b) = (0, 0)
            if not k & 1:
                for l in range(m):
                    if s[f(k, l)] == c1[l & 1]:
                        a += 1
                    elif s[f(k, l)] == c1[l & 1 ^ 1]:
                        b += 1
            else:
                for l in range(m):
                    if s[f(k, l)] == c2[l & 1]:
                        a += 1
                    elif s[f(k, l)] == c2[l & 1 ^ 1]:
                        b += 1
            c += max(a, b)
        if ma1 < c:
            (ma1, m1, m2) = (c, c1, c2)
(ma2, m3, m4) = (-1, [], [])
for i in range(4):
    for j in range(i + 1, 4):
        (c1, c2) = ([i, j], [])
        for k in range(4):
            if i ^ k and j ^ k:
                c2.append(k)
        c = 0
        for l in range(m):
            (a, b) = (0, 0)
            if not l & 1:
                for k in range(n):
                    if s[f(k, l)] == c1[k & 1]:
                        a += 1
                    elif s[f(k, l)] == c1[k & 1 ^ 1]:
                        b += 1
            else:
                for k in range(n):
                    if s[f(k, l)] == c2[k & 1]:
                        a += 1
                    elif s[f(k, l)] == c2[k & 1 ^ 1]:
                        b += 1
            c += max(a, b)
        if ma2 < c:
            (ma2, m3, m4) = (c, c1, c2)
ans0 = [0] * (n * m)
if ma1 >= ma2:
    c = 0
    (c1, c2) = (m1, m2)
    for k in range(n):
        (a, b) = (0, 0)
        if not k & 1:
            for l in range(m):
                if s[f(k, l)] == c1[l & 1]:
                    a += 1
                elif s[f(k, l)] == c1[l & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for l in range(m):
                ans0[f(k, l)] = c1[l & 1 ^ i]
        else:
            for l in range(m):
                if s[f(k, l)] == c2[l & 1]:
                    a += 1
                elif s[f(k, l)] == c2[l & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for l in range(m):
                ans0[f(k, l)] = c2[l & 1 ^ i]
else:
    c = 0
    (c1, c2) = (m3, m4)
    for l in range(m):
        (a, b) = (0, 0)
        if not l & 1:
            for k in range(n):
                if s[f(k, l)] == c1[k & 1]:
                    a += 1
                elif s[f(k, l)] == c1[k & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for k in range(n):
                ans0[f(k, l)] = c1[k & 1 ^ i]
        else:
            for k in range(n):
                if s[f(k, l)] == c2[k & 1]:
                    a += 1
                elif s[f(k, l)] == c2[k & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for k in range(n):
                ans0[f(k, l)] = c2[k & 1 ^ i]
ans = ['?'] * n
for i in range(n):
    ans1 = ''.join([u[ans0[j]] for j in range(i * m, (i + 1) * m)])
    ans[i] = ans1
sys.stdout.write('\n'.join(ans))
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 = 1000000.0
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])])
    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:
            pattern[i] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = True
        bl = l
    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('\n'.join((''.join((k for k in grid[i])) for i in range(ly))))
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 = 1000000.0
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])])
    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:
            pattern[i] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = True
        bl = l
    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)])
stdout.write('\n'.join((''.join((k for k in grid[i])) for i in range(ly))))