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.
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
grid=[]
for i in range(n):
  s=input()
  grid.append([])
  for j in range(m):
    if s[j]=='A':
      grid[-1].append(0)
    elif s[j]=='C':
      grid[-1].append(1)
    elif s[j]=='G':
      grid[-1].append(2)
    else:
      grid[-1].append(3)
bestscore=n*m
rowsum0=[]
rowsum1=[]
for i in range(n):
  rowsum0.append([0]*4)
  rowsum1.append([0]*4)
columnsum0=[]
columnsum1=[]
for i in range(m):
  columnsum0.append([0]*4)
  columnsum1.append([0]*4)
for i in range(n):
  for j in range(m):
    if j%2==0:
      rowsum0[i][grid[i][j]]+=1
    else:
      rowsum1[i][grid[i][j]]+=1
    if i%2==0:
      columnsum0[j][grid[i][j]]+=1
    else:
      columnsum1[j][grid[i][j]]+=1
flag=0
bestx=-1
besty=-1
for x in range(3):
  for y in range(x+1,4):
    for i in range(4):
      if i!=x and i!=y:
        p=i
        break
    for i in range(4):
      if i!=x and i!=y and i!=p:
        q=i
        break
    tmpscore=0
    for i in range(n):
      if i%2==0:
        tmpscore+=m-max(rowsum0[i][x]+rowsum1[i][y],rowsum0[i][y]+rowsum1[i][x])
      else:
        tmpscore+=m-max(rowsum0[i][p]+rowsum1[i][q],rowsum0[i][q]+rowsum1[i][p])
    if bestscore>tmpscore:
      flag=0
      bestx=x
      besty=y
      bestscore=tmpscore
for x in range(3):
  for y in range(x+1,4):
    for i in range(4):
      if i!=x and i!=y:
        p=i
        break
    for i in range(4):
      if i!=x and i!=y and i!=p:
        q=i
        break
    tmpscore=0
    for i in range(m):
      if i%2==0:
        tmpscore+=n-max(columnsum0[i][x]+columnsum1[i][y],columnsum0[i][y]+columnsum1[i][x])
      else:
        tmpscore+=n-max(columnsum0[i][p]+columnsum1[i][q],columnsum0[i][q]+columnsum1[i][p])
    if bestscore>tmpscore:
      flag=1
      bestx=x
      besty=y
      bestscore=tmpscore
ans=[]
for i in range(n):
  ans.append([0]*m)
x=bestx
y=besty
conv='ACGT'
if flag:
  for i in range(4):
    if i!=x and i!=y:
      p=i
      break
  for i in range(4):
    if i!=x and i!=y and i!=p:
      q=i
      break
  for i in range(m):
    if i%2==0:
      if columnsum0[i][y]+columnsum1[i][x]>columnsum0[i][x]+columnsum1[i][y]:
        tmp=x
        x=y
        y=tmp
      for j in range(n):
        if j%2==0:
          ans[j][i]=conv[x]
        else:
          ans[j][i]=conv[y]
    else:
      if columnsum0[i][q]+columnsum1[i][p]>columnsum0[i][p]+columnsum1[i][q]:
        tmp=p
        p=q
        q=tmp
      for j in range(n):
        if j%2==0:
          ans[j][i]=conv[p]
        else:
          ans[j][i]=conv[q]
else:
  for i in range(4):
    if i!=x and i!=y:
      p=i
      break
  for i in range(4):
    if i!=x and i!=y and i!=p:
      q=i
      break
  for i in range(n):
    if i%2==0:
      if rowsum0[i][y]+rowsum1[i][x]>rowsum0[i][x]+rowsum1[i][y]:
        tmp=x
        x=y
        y=tmp
      for j in range(m):
        if j%2==0:
          ans[i][j]=conv[x]
        else:
          ans[i][j]=conv[y]
    else:
      if rowsum0[i][q]+rowsum1[i][p]>rowsum0[i][p]+rowsum1[i][q]:
        tmp=p
        p=q
        q=tmp
      for j in range(m):
        if j%2==0:
          ans[i][j]=conv[p]
        else:
          ans[i][j]=conv[q]
for i in range(n):
  print(''.join(ans[i]))