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;
mt19937 gen_rand;
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &a) {
  os << "(";
  os << a.first << ", ";
  os << a.second;
  os << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
  os << "{";
  bool was = false;
  for (auto &x : a) {
    if (was) {
      os << ", ";
    }
    was = true;
    os << x;
  }
  os << "}";
  return os;
}
template <typename T>
inline void debug(const char *sdbg, T x) {
  cerr << "The value of " << sdbg << " is " << x << "\n";
};
template <typename T, typename... U>
inline void debug(const char *sdbg, T h, U... t) {
  cerr << "The value of ";
  while (*sdbg != ',') {
    cerr << *sdbg++;
  }
  cerr << " is " << h << "\n";
  debug(sdbg + 1, t...);
  cerr << "\n";
}
template <typename T>
T abs(T x) {
  if (x < 0) {
    return -x;
  } else {
    return x;
  }
}
template <typename T>
T sqr(T x) {
  return x * x;
};
const long long INF_FOR_SHORT_TIME = (long long)(1e9);
template <typename T>
T mul(T a, T b, T m) {
  if (a <= INF_FOR_SHORT_TIME && b <= INF_FOR_SHORT_TIME) {
    return (a * b) % m;
  }
  T q = (long long)((long double)a * (long double)b / (long double)m);
  T r = a * b - q * m;
  return (r + 5 * m) % m;
}
template <typename T, typename U>
T binpow(T a, U n, T MOD) {
  T res = 1;
  while (n) {
    if (n & 1) {
      res = mul(res, a, MOD);
    }
    a = mul(a, a, MOD);
    n >>= 1;
  }
  return res;
};
template <typename T>
int sign(T x) {
  if (x < 0) {
    return -1;
  } else if (x > 0) {
    return 1;
  } else {
    return 0;
  }
};
template <typename T>
T gcd(T a, T b) {
  if (a > b) {
    swap(a, b);
  }
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
};
template <typename T>
bool uin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
template <typename T>
bool uax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
};
int rev(char c) {
  if (c == 'A') {
    return 0;
  } else if (c == 'C') {
    return 1;
  } else if (c == 'G') {
    return 2;
  } else {
    return 3;
  }
}
char rev(int c) {
  if (c == 0) {
    return 'A';
  } else if (c == 1) {
    return 'C';
  } else if (c == 2) {
    return 'G';
  } else {
    return 'T';
  }
}
struct mtr {
  int n, m;
  vector<vector<int>> a;
  void clr() {
    n = 0;
    m = 0;
    a.clear();
  }
  void read() {
    cin >> n >> m;
    a.resize(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        char c;
        cin >> c;
        a[i][j] = rev(c);
      }
    }
  }
  void cpy(mtr &x) {
    n = x.n;
    m = x.m;
    a = x.a;
  }
  void rot() {
    vector<vector<int>> b(m, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        b[m - j - 1][i] = a[i][j];
      }
    }
    swap(n, m);
    swap(a, b);
  }
  void print() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cout << rev(a[i][j]);
      }
      cout << "\n";
    }
    cout << "\n";
  }
};
pair<int, mtr> solve(mtr m) {
  mtr res, cur;
  cur.cpy(m);
  res.cpy(m);
  int cnt = m.n * m.m + 1;
  for (int vf = 1; vf < 4; ++vf) {
    for (int vs = 0; vs < vf; ++vs) {
      vector<vector<int>> to(2);
      to[0] = {vf, vs};
      for (int i = 0; i < 4; ++i) {
        if (vf == i || vs == i) {
          continue;
        }
        to[1].push_back(i);
      }
      int cur_cnt = 0;
      for (int i = 0; i < m.n; ++i) {
        int cur0 = 0;
        int cur1 = 0;
        for (int j = 0; j < m.m; ++j) {
          if (m.a[i][j] == to[i & 1][j & 1]) {
            ++cur0;
          }
          if (m.a[i][j] == to[i & 1][(j & 1) ^ 1]) {
            ++cur1;
          }
        }
        int buf = 0;
        if (uax(cur0, cur1)) {
          buf = 1;
        }
        cur_cnt += (m.m - cur0);
        for (int j = 0; j < m.m; ++j) {
          cur.a[i][j] = to[i & 1][(j & 1) ^ buf];
        }
      }
      if (uin(cnt, cur_cnt)) {
        res = cur;
      }
    }
  }
  return make_pair(cnt, res);
}
int main() {
  gen_rand.seed(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  mtr m;
  m.read();
  auto res = solve(m);
  m.rot();
  auto new_res = solve(m);
  if (res.first < new_res.first) {
    res.second.print();
  } else {
    new_res.second.rot();
    new_res.second.rot();
    new_res.second.rot();
    new_res.second.print();
  }
  return 0;
}
