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.util.*;
import java.util.stream.*;

public class B {

	public Object solve () {
		int R = sc.nextInt(), C = sc.nextInt();

		char [][] A = sc.nextChars(R);
		char [][] B = new char[C][R];
		for (int i : rep(R))
			for (int j : rep(C))
				B[j][i] = A[i][j];

		char [][] X = calc(A);
		char [][] Y = calc(B);

		int v = val(A, X);
		int w = val(B, Y);

		if (v <= w)
			for (char [] a : X)
				print(new String(a));
		// err(v);
		else
			for (int i : rep(R)) {
				StringBuilder Z = new StringBuilder();
				for (int j : rep(C))
					Z.append(Y[j][i]);
				print(Z);
			}
		// err(w);

		return null;
	}

	char [][] calc(char [][] A) {
		char [] Q = { 'A', 'C', 'G', 'T' };
		int R = A.length, C = A[0].length;

		char [][] res = null; int VAL = INF;

		for (int [] p : permutations(4)) {
			if (p[0] > p[1]) continue;
			if (p[2] > p[3]) continue;

			char [][] X = new char [R][C]; int val = 0;
			for (int r : rep(R)) {
				int m = (r % 2);
				char [] W = { Q[p[2*m]], Q[p[2*m+1]] };

				int [] V = { 0, 0 };
				for (int j : rep(2))
					for (int c : rep(C))
						if (A[r][c] != W[(c+j) % 2])
							++V[j];

				int j = V[0] < V[1] ? 0 : 1;
				for (int c : rep(C))
					X[r][c] = W[(c+j) % 2];
				val += V[j];
			}

			if (val < VAL) {
				VAL = val;
				res = X;
			}
		}

		return res;
	}

	int val(char [][] A, char [][] X) {
		int R = A.length, C = A[0].length, res = 0;
		for (int r : rep(R))
			for (int c : rep(C))
				if (A[r][c] != X[r][c])
					++res;
		return res;
	}
	private static final boolean ONE_TEST_CASE = true;

	private static void init () {
	}

	private static final int INF = (int) 1e9 + 10;
	private static int [] nextPermutation (int [] P) {
		int N = P.length;
		for (int i = N-1; i > 0; --i)
			if (P[i-1] < P[i]) {
				reverse(P, i, N);
				for (int j = i; j < N; ++j)
					if (P[j] > P[i-1]) {
						int x = P[i-1], y = P[j];
						P[j] = x; P[i-1] = y;
						return P;
					}
			}
		return null;
	}
	private static Iterable<int[]> permutations (final int N) {
		return new Iterable<int[]>() {
			@Override
			public Iterator<int[]> iterator() {
				return new Iterator<int[]>() {
					int [] P = null;

					@Override
					public boolean hasNext() {
						if (P == null)
							return true;
						for (int i = 0; i < N; ++i)
							if (i + P[i] != N - 1)
								return true;
						return false;
					}

					@Override
					public int[] next() {
						if (P == null)
							return P = singletons(N);
						else if ((P = nextPermutation(P)) == null)
							throw new NoSuchElementException();
						else
							return P;
					}
				};
			}
		};
	}
	private static int [] rep (int N) { return rep(0, N); }
	private static int [] rep (int S, int T) { if (S >= T) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] reverse (int [] A, int s, int t) {
		for (int i = 0; 2*i < t - s - 1; ++i) {
			int x = A[s+i], y = A[t-i-1];
			A[s+i] = y; A[t-i-1] = x;
		}
		return A;
	}
	private static int [] singletons (int N) { int [] res = new int [N]; for (int i = 0; i < N; ++i) res[i] = i; return res; }
	//////////////////////////////////////////////////////////////////////////////////// OFF
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static Object print (Object o, Object ... A) { IOUtils.print(o, A); return null; }
	private static class IOUtils {
		public static class MyScanner {
			public String next () { newLine(); return line[index++]; }
			public int nextInt () { return Integer.parseInt(next()); }
			public char [] nextChars () { return next ().toCharArray (); }
			public char[][] nextChars (int N) { return IntStream.range(0, N).mapToObj(i -> nextChars()).toArray(char[][]::new); }
			//////////////////////////////////////////////
			private boolean eol () { return index == line.length; }
			private String readLine () {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine () {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split (String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build (Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim (String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static final java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");
		private static void start () { if (t == 0) t = millis(); }
		private static void append (java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g, final Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			}
			else if (o instanceof Iterable<?>)
				((Iterable<?>)o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}
		private static void append (final StringBuilder b, Object o, final String delim) {
			append(x -> { append(b, x, delim); }, x -> b.append(delim).append(x), o);
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print (Object o, Object ... A) {
			pw.println(build(o, A));
			if (DEBUG)
				pw.flush();
		}
		private static void err (Object o, Object ... A) { System.err.println(build(o, A)); }
		private static boolean DEBUG;
		private static void write (Object o) {
			err(o, '(', time(), ')');
			if (!DEBUG)
				pw.println(o);
		}
		private static void exit () {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(time());
			System.exit(0);
		}
		private static long t;
		private static long millis () { return System.currentTimeMillis(); }
		private static String time () { return "Time: " + (millis() - t) / 1000.0; }
		private static void run (int N) {
			try { DEBUG = System.getProperties().containsKey("DEBUG"); }
			catch (Throwable t) {}

			for (int n = 1; n <= N; ++n) {
				Object res = new B().solve();
				if (res != null)
					write("Case #" + n + ": " + build(res));
			}
			exit();
		}
	}
	////////////////////////////////////////////////////////////////////////////////////
	public static void main (String[] args) {
		init();
		int N = ONE_TEST_CASE ? 1 : sc.nextInt();
		IOUtils.run(N);
	}
}
