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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sumit
 */
public class Main {
      public static void main(String[] args) {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            InputReader in = new InputReader(inputStream);
            OutputWriter out = new OutputWriter(outputStream);
            ENiceTable solver = new ENiceTable();
            solver.solve(1, in, out);
            out.close();
      }

      static class ENiceTable {
            int n;
            int m;
            String[] str;
            char[] given = {'A', 'G', 'C', 'T'};
            int res = Integer.MAX_VALUE;
            String[] s1;
            String[] s2;

            int check(String st, String t1) {
                  int count = 0;
                  for (int i = 0; i < st.length(); i++) {
                        if (st.charAt(i) != t1.charAt(i))
                              count++;
                  }
                  return count;
            }

            String fill(String st, char c1, char c2) {
                  StringBuilder t1 = new StringBuilder();
                  StringBuilder t2 = new StringBuilder();
                  for (int i = 0; i < st.length(); i++) {
                        if (i % 2 == 0) {
                              t1.append(c1);
                              t2.append(c2);
                        } else {
                              t1.append(c2);
                              t2.append(c1);
                        }
                  }
                  if (check(st, t1.toString()) > check(st, t2.toString())) {
                        return t2.toString();
                  } else
                        return t1.toString();
            }

            void solve2(char c1, char c2) {
                  char c3 = ' ', c4 = ' ';
                  String temp[] = new String[m];
                  int tmp = 0;
                  for (int i = 0; i < 4; i++)
                        if (given[i] != c1 && given[i] != c2)
                              c3 = given[i];
                  for (int i = 0; i < 4; i++)
                        if (given[i] != c1 && given[i] != c2 && given[i] != c3)
                              c4 = given[i];

                  for (int i = 0; i < m; i++) {
                        StringBuilder tt = new StringBuilder();
                        for (int j = 0; j < n; j++)
                              tt.append(str[j].charAt(i));
                        if (i % 2 == 0) {
                              temp[i] = fill(tt.toString(), c1, c2);
                              tmp += check(tt.toString(), temp[i]);
                        } else {
                              temp[i] = fill(tt.toString(), c3, c4);
                              tmp += check(tt.toString(), temp[i]);
                        }
                  }

                  if (tmp < res) {
                        res = tmp;

                        for (int i = 0; i < n; i++) {
                              StringBuilder tt = new StringBuilder();
                              for (int j = 0; j < m; j++) {
                                    tt.append(temp[j].charAt(i));
                              }
                              s1[i] = tt.toString();
                        }
                  }
            }

            void solve1(char c1, char c2) {
                  char c3 = ' ', c4 = ' ';
                  String temp[] = new String[n];
                  int tmp = 0;
                  for (int i = 0; i < 4; i++)
                        if (given[i] != c1 && given[i] != c2)
                              c3 = given[i];
                  for (int i = 0; i < 4; i++)
                        if (given[i] != c1 && given[i] != c2 && given[i] != c3)
                              c4 = given[i];
                  for (int i = 0; i < n; i++) {
                        if (i % 2 == 0) {
                              temp[i] = fill(str[i], c1, c2);
                              tmp += check(str[i], temp[i]);
                        } else {
                              temp[i] = fill(str[i], c3, c4);
                              tmp += check(str[i], temp[i]);
                        }
                  }

                  if (tmp < res) {
                        res = tmp;
                        for (int i = 0; i < n; i++) {
                              s1[i] = temp[i];
                        }

                  }
            }

            public void solve(int testNumber, InputReader in, OutputWriter out) {
                  n = in.nextInt();
                  m = in.nextInt();
                  str = new String[n];
                  s1 = new String[n];
                  s2 = new String[n];
                  for (int i = 0; i < n; i++)
                        str[i] = in.next();

                  solve1('A', 'G');
                  solve1('A', 'C');
                  solve1('A', 'T');
                  solve1('C', 'T');
                  solve1('G', 'C');
                  solve1('G', 'T');
                  solve2('A', 'G');
                  solve2('A', 'C');
                  solve2('A', 'T');
                  solve2('C', 'T');
                  solve2('G', 'C');
                  solve2('G', 'T');

                  for (int i = 0; i < n; i++)
                        out.printLine(s1[i]);

            }

      }

      static class OutputWriter {
            private final PrintWriter writer;

            public OutputWriter(OutputStream outputStream) {
                  writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }

            public OutputWriter(Writer writer) {
                  this.writer = new PrintWriter(writer);
            }

            public void print(Object... objects) {
                  for (int i = 0; i < objects.length; i++) {
                        if (i != 0) {
                              writer.print(' ');
                        }
                        writer.print(objects[i]);
                  }
            }

            public void printLine(Object... objects) {
                  print(objects);
                  writer.println();
            }

            public void close() {
                  writer.close();
            }

      }

      static class InputReader {
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;

            public InputReader(InputStream stream) {
                  this.stream = stream;
            }

            public int read() {
                  if (numChars == -1)
                        throw new InputMismatchException();

                  if (curChar >= numChars) {
                        curChar = 0;
                        try {
                              numChars = stream.read(buf);
                        } catch (IOException e) {
                              throw new InputMismatchException();
                        }
                        if (numChars <= 0)
                              return -1;
                  }

                  return buf[curChar++];
            }

            public int nextInt() {
                  int c = read();

                  while (isSpaceChar(c))
                        c = read();

                  int sgn = 1;

                  if (c == '-') {
                        sgn = -1;
                        c = read();
                  }

                  int res = 0;

                  do {
                        if (c < '0' || c > '9')
                              throw new InputMismatchException();

                        res *= 10;
                        res += c & 15;

                        c = read();
                  } while (!isSpaceChar(c));

                  return res * sgn;
            }

            public String next() {
                  int c = read();

                  while (isSpaceChar(c))
                        c = read();

                  StringBuilder res = new StringBuilder();

                  do {
                        res.appendCodePoint(c);

                        c = read();
                  } while (!isSpaceChar(c));

                  return res.toString();
            }

            public boolean isSpaceChar(int c) {
                  return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }

      }
}

