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.
#include <bits/stdc++.h>
using namespace std;
template <typename S, typename T>
ostream& operator<<(ostream& out, pair<S, T> const& p) {
  out << '(' << p.first << ", " << p.second << ')';
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& v) {
  long long l = v.size();
  for (long long i = 0; i < l - 1; i++) out << v[i] << ' ';
  if (l > 0) out << v[l - 1];
  return out;
}
template <typename T>
void trace(const char* name, T&& arg1) {
  cout << name << " : " << arg1 << "\n";
}
template <typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  trace(comma + 1, args...);
}
long long n, m;
vector<string> arr;
map<long long, char> let;
vector<string> res;
long long best = 1000000000000000001;
long long aa, bb, cc, dd;
bool col;
long long try_row(long long r, long long a, long long b) {
  char f = let[a];
  char s = let[b];
  long long ans = 0;
  for (long long i = 0; i < m; i++) {
    ans += (arr[r][i] != f);
    swap(f, s);
  }
  return ans;
}
long long try_rows(long long a, long long b, long long c, long long d) {
  long long ans = 0;
  for (long long i = 0; i < n; i++) {
    ans += min(try_row(i, a, b), try_row(i, b, a));
    swap(a, c), swap(b, d);
  }
  return ans;
}
long long try_col(long long r, long long a, long long b) {
  char f = let[a];
  char s = let[b];
  long long ans = 0;
  for (long long i = 0; i < n; i++) {
    ans += (arr[i][r] != f);
    swap(f, s);
  }
  return ans;
}
long long try_cols(long long a, long long b, long long c, long long d) {
  long long ans = 0;
  for (long long i = 0; i < m; i++) {
    ans += min(try_col(i, a, b), try_col(i, b, a));
    swap(a, c), swap(b, d);
  }
  return ans;
}
void fill_col(long long r, long long a, long long b) {
  char f = let[a];
  char s = let[b];
  for (long long i = 0; i < n; i++) {
    res[i][r] = f;
    swap(f, s);
  }
}
void fill_cols(long long a, long long b, long long c, long long d) {
  string temp = "";
  for (long long i = 0; i < m; i++) {
    temp += "*";
  }
  for (long long i = 0; i < n; i++) {
    res.push_back(temp);
  }
  for (long long i = 0; i < m; i++) {
    if (try_col(i, a, b) < try_col(i, b, a)) {
      fill_col(i, a, b);
    } else {
      fill_col(i, b, a);
    }
    swap(a, c), swap(b, d);
  }
}
void fill_row(long long r, long long a, long long b) {
  char f = let[a];
  char s = let[b];
  for (long long i = 0; i < m; i++) {
    res[r][i] = f;
    swap(f, s);
  }
}
void fill_rows(long long a, long long b, long long c, long long d) {
  string temp = "";
  for (long long i = 0; i < m; i++) {
    temp += "*";
  }
  for (long long i = 0; i < n; i++) {
    res.push_back(temp);
  }
  for (long long i = 0; i < n; i++) {
    if (try_row(i, a, b) < try_row(i, b, a)) {
      fill_row(i, a, b);
    } else {
      fill_row(i, b, a);
    }
    swap(a, c), swap(b, d);
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for (long long i = 0; i < n; i++) {
    string temp;
    cin >> temp;
    arr.push_back(temp);
  }
  let[0] = 'T';
  let[1] = 'A';
  let[2] = 'G';
  let[3] = 'C';
  for (long long a = 0; a < 4; a++) {
    for (long long b = 0; b < 4; b++) {
      for (long long c = 0; c < 4; c++) {
        for (long long d = 0; d < 4; d++) {
          set<long long> s;
          s.insert({a, b, c, d});
          if ((long long)s.size() == 4) {
            long long lol = try_rows(a, b, c, d);
            if (lol < best) {
              best = lol;
              aa = a;
              bb = b;
              cc = c;
              dd = d;
              col = false;
            }
            lol = try_cols(a, b, c, d);
            if (lol < best) {
              best = lol;
              aa = a;
              bb = b;
              cc = c;
              dd = d;
              col = true;
            }
          }
        }
      }
    }
  }
  if (col == true) {
    fill_cols(aa, bb, cc, dd);
    for (long long i = 0; i < n; i++) {
      cout << res[i] << "\n";
    }
  } else {
    fill_rows(aa, bb, cc, dd);
    for (long long i = 0; i < n; i++) {
      cout << res[i] << "\n";
    }
  }
}
