#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <assert.h>

using namespace std;

struct State {
  int player;
  int qx;
  int qy;
  int ax;
  int ay;
  State() {;}
  State(int p, int y1, int x1, int y2, int x2) : player(p), qx(x1), qy(y1), ax(x2), ay(y2) {;}
};

char field[50][50];

static const int QTURN = 0;
static const int ATURN = 1;

static const int UNKONWN = 0;
static const int QWIN = 1;
static const int UNKNOWN = 0;
static const int AWIN = -1;

int temp1[100000];
int win[2][40][40][40][40];
int temp2[100000];
int width;
int height;

inline bool can_move(int x, int y) {
  return field[y][x] != '#';
}

int main() {
  while (true) {
  memset(field, '#', sizeof(field));
  memset(win, 0, sizeof(win));
  scanf("%d %d", &width, &height);
if (width == 0) { return 0; }
  for (int y = 1; y <= height; y++) {
    scanf("%s", &field[y][1]);
    field[y][width + 1] = '#';
  }
  int qstartx;
  int qstarty;
  int astartx;
  int astarty;
  int dx[5] = { 1, -1, 0, 0, 0 };
  int dy[5] = { 0, 0, 1, -1, 0 };
  queue<State> que;
  for (int y = 1; y <= height; y++) {
    for (int x = 1; x <= width; x++) {
      if (field[y][x] == 'Q') {
        qstartx = x;
        qstarty = y;
      } else if (field[y][x] == 'A')  {
        astartx = x;
        astarty = y;
      } else if (field[y][x] == 'E') {
        for (int i = 1; i <= height; i++) {
          for (int j = 1; j <= width; j++) {
            if (y == i && x == j) { continue; }
            if (!can_move(j, i)) { continue; }
            win[QTURN][y][x][i][j] = QWIN;;
            for (int k = 0; k < 5; k++) {
              int nx = j + dx[k];
              int ny = i + dy[k];
              if (!can_move(nx, ny)) { continue; }
              que.push(State(ATURN, y, x, ny, nx));
            }
          }
        }
      }
      if (!can_move(x, y)) { continue; }
      win[QTURN][y][x][y][x] = AWIN;
      win[ATURN][y][x][y][x] = AWIN;
      for (int k = 0; k < 5; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (!can_move(nx, ny)) { continue; }
        que.push(State(ATURN, y, x, ny, nx));
        que.push(State(QTURN, ny, nx, y, x));
      }
    }
  }
  while (!que.empty()) {
    State state = que.front();
    que.pop();
    if (win[state.player][state.qy][state.qx][state.ay][state.ax] != UNKNOWN) { continue; }
      //cout << state.player << " " << state.qx << " " << state.ax << endl;
    int next_turn = (state.player + 1) & 1;
    bool qwin = false;
    bool unknown = false;
    bool awin = false;
    for (int i = 0; i < 5; i++) {
      int next;
      int nx;
      int ny;
      if (state.player == QTURN) {
        nx = state.qx + dx[i];
        ny = state.qy + dy[i];
        if (!can_move(nx, ny)) { continue; }
        next = win[next_turn][ny][nx][state.ay][state.ax];
      } else {
        nx = state.ax + dx[i];
        ny = state.ay + dy[i];
        if (!can_move(nx, ny)) { continue; }
        next = win[next_turn][state.qy][state.qx][ny][nx];
      }
      switch (next) {
        case QWIN:
          qwin = true;
          break;
        case AWIN:
          awin = true;
          break;
        case UNKNOWN:
          unknown = true;
          break;
        default:
          assert(false);
      }
    }
    if (state.player == QTURN) {
      if (qwin) {
        win[state.player][state.qy][state.qx][state.ay][state.ax] = QWIN;
      } else if (!unknown) {
        win[state.player][state.qy][state.qx][state.ay][state.ax] = AWIN;
      }
    } else {
      if (awin) {
        win[state.player][state.qy][state.qx][state.ay][state.ax] = AWIN;
      } else if (!unknown) {
        win[state.player][state.qy][state.qx][state.ay][state.ax] = QWIN;
      }
    }
    if (win[state.player][state.qy][state.qx][state.ay][state.ax] != UNKNOWN) {
      //cout << state.player << " " << state.qx << " " << state.ax << " " << win[state.player][state.qy][state.qx][state.ay][state.ax] << endl;
      //cout << state.player << " " << state.qx << " " << state.qy << " " << state.ax << " " << state.ay << " " << win[state.player][state.qy][state.qx][state.ay][state.ax] << endl;
      if (state.player == QTURN) {
        for (int i = 0; i < 5; i++) {
          int nx = state.ax + dx[i];
          int ny = state.ay + dy[i];
          if (!can_move(nx, ny)) { continue; }
          if (win[next_turn][state.qy][state.qx][ny][nx] != UNKNOWN) { continue; }
          que.push(State(ATURN, state.qy, state.qx, ny, nx));
        }
      } else {
        for (int i = 0; i < 5; i++) {
          int nx = state.qx + dx[i];
          int ny = state.qy + dy[i];
          if (!can_move(nx, ny)) { continue; }
          if (win[next_turn][ny][nx][state.ay][state.ax] != UNKNOWN) { continue; }
          que.push(State(QTURN, ny, nx, state.ay, state.ax));
        }
      }
    }
  }
  switch (win[QTURN][qstarty][qstartx][astarty][astartx]) {
    case QWIN:
      printf("Queen can escape.\n");
      break;
    case AWIN:
      printf("Army can catch Queen.\n");
      break;
    case UNKNOWN:
      printf("Queen can not escape and Army can not catch Queen.\n");
      break;
    default:
      assert(false);
  }
}
}

Measured memory_bytes: 20000