#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax = 30 + 1;
const int dx[5] = {0, 0, 1, -1, 0};
const int dy[5] = {1, -1, 0, 0, 0};

struct state {
	int x1, y1, x2, y2;
	bool turn; // 0 for Q ed
	state() {};
	state(int _x1, int _y1, int _x2, int _y2, bool _turn) {
		x1 = _x1, x2 = _x2, y1 = _y1, y2 = _y2, turn = _turn;
	}
	void init(int _x1, int _y1, int _x2, int _y2, bool _turn) {
		x1 = _x1, x2 = _x2, y1 = _y1, y2 = _y2, turn = _turn;
	}
};

bool f[nmax][nmax][nmax][nmax][2]; // 0 for lose
vector<state> Q;
bool ed[nmax][nmax][nmax][nmax][2];
char a[nmax][nmax];
int n, m;

int check(state &s)
{
	int x1, x2, y1, y2;
	int nxtt = s.turn ^ 1;
	bool all = 1, exist = 0;
	if (s.turn == 0) {
		x1 = s.x1, y1 = s.y1;
		for (int j = 0; j < 5; ++j) {
			x2 = s.x2 + dx[j], y2 = s.y2 + dy[j];
			if (x2 <= 0 || x2 > n || y2 <= 0 || y2 > m || a[x2][y2] == '#') continue;
			if (!ed[x1][y1][x2][y2][nxtt]) {
				all = 0;
				continue;
			}
			if (f[x1][y1][x2][y2][nxtt] == 0)
				exist = 1, all = 0;
		}
	}
	else {
		for (int i = 0; i < 5; ++i) {
			x1 = s.x1 + dx[i], y1 = s.y1 + dy[i];
			if (x1 <= 0 || x1 > n || y1 <= 0 || y1 > m || a[x1][y1] == '#') continue;
			x2 = s.x2, y2 = s.y2;
			if (!ed[x1][y1][x2][y2][nxtt]) {
				all = 0;
				continue;
			}
			if (f[x1][y1][x2][y2][nxtt] == 1)
				exist = 1, all = 0;
		}
	}
	if (all)
		return nxtt;
	else if (exist)
		return s.turn;
	else return 2;
}

int main()
{
	while (1) {
		scanf("%d%d", &n, &m);
		swap(n, m);
		if (n == 0 && m == 0) break;
		for (int i = 1; i <= n; ++i)
			scanf("%s", a[i] + 1);
		memset(ed, 0, sizeof(ed));
		Q.clear();
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) if (a[i][j] != '#')
				for (int k = 1; k <= n; ++k)
					for (int l = 1; l <= m; ++l) if (a[k][l] != '#') {
						if (i == k && j == l) {
							state tmp(i, j, k, l, 1);
							Q.push_back(tmp);
							f[i][j][k][l][1] = 0;
							ed[i][j][k][l][1] = 1;
						}
						else if (a[i][j] == 'E') {
							state tmp(i, j, k, l, 1);
							Q.push_back(tmp);
							f[i][j][k][l][1] = 1;
							ed[i][j][k][l][1] = 1;
						}
					}
//		printf("hah\n");
		state tmp;
		for (int tmpi = 0; tmpi < Q.size(); ++tmpi) {
//			printf("%d\n", (int)Q.size());
			state now = Q[tmpi];
			int x1, x2, y1, y2, tmpf;
//			printf("(%d) (%d) %d: %d\n", now->y1, now->y2, now->turn, f[now->x1][now->y1][now->x2][now->y2][now->turn]);
//			printf("(%d, %d) (%d, %d) %d: %d\n", now->x1, now->y1, now->x2, now->y2, now->turn, f[now->x1][now->y1][now->x2][now->y2][now->turn]);
			bool nxtt = now.turn ^ 1;
			if (now.turn == 1) {
				x1 = now.x1, y1 = now.y1;
				for (int j = 0; j < 5; ++j) {
//					printf("hehe in\n");
					x2 = now.x2 + dx[j], y2 = now.y2 + dy[j];
//					printf("hehe out\n");
					if (x2 <= 0 || x2 > n || y2 <= 0 || y2 > m || a[x2][y2] == '#') continue;
					if (ed[x1][y1][x2][y2][nxtt]) continue;
					tmp.init(x1, y1, x2, y2, nxtt);
					if ((tmpf = check(tmp)) != 2) {
						ed[x1][y1][x2][y2][nxtt] = 1;
						f[x1][y1][x2][y2][nxtt] = tmpf;
						Q.push_back(tmp);
					}
				}
			}
			else {
				for (int i = 0; i < 5; ++i) {
					x1 = now.x1 + dx[i], y1 = now.y1 + dy[i];
					if (x1 <= 0 || x1 > n || y1 <= 0 || y1 > m || a[x1][y1] == '#') continue;
					x2 = now.x2, y2 = now.y2;
					if (ed[x1][y1][x2][y2][nxtt]) continue;
					tmp.init(x1, y1, x2, y2, nxtt);
					if ((tmpf = check(tmp)) != 2) {
						ed[x1][y1][x2][y2][nxtt] = 1;
						f[x1][y1][x2][y2][nxtt] = tmpf;
						Q.push_back(tmp);
					}
				}
			}
		}
		int lx, ly, rx, ry;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
				if (a[i][j] == 'Q')
					lx = i, ly = j;
				if (a[i][j] == 'A')
					rx = i, ry = j;
			}
		if (!ed[lx][ly][rx][ry][1])
			printf("Queen can not escape and Army can not catch Queen.\n"); // tie
		else
			if (f[lx][ly][rx][ry][1])
				printf("Queen can escape.\n"); //win
			else
				printf("Army can catch Queen.\n"); //lose
	}
	return 0;
}

Measured memory_bytes: 4628