레이싱 카의 궤적

앨리스와 밥은 트론(Tron)에서 영감을 받은 자동차 경주 게임을 즐긴다. 정사각형 격자 위를 자동차 한 대가 달리며, 격자에 놓인 장애물을 피해야 한다. 또한 자동차는 지나간 모든 칸에 지워지지 않는 궤적을 남기므로, 이 궤적도 피해야 한다. 자동차는 한 번에 한 칸씩 동·서·남·북 네 방향으로만 움직인다.

두 사람은 같은 자동차를 번갈아 조종한다. 항상 앨리스가 먼저 움직이며, 현재 칸에서 인접한 칸으로 자동차를 옮긴다. 그다음 밥이 다시 인접한 칸으로 옮기고, 다시 앨리스가 옮기는 식으로 진행한다.

한 번 지나간 칸은 궤적으로 막혀 다시는 들어갈 수 없다. 자기 차례에는 비어 있고 아직 지나가지 않은 인접한 칸으로 자동차를 옮겨야 한다. 그런 칸이 하나도 없는 사람은 충돌할 수밖에 없어 즉시 패배한다. 두 사람 모두 완벽하게 플레이하여 피할 수 있는 실수는 하지 않는다. 즉, 어느 방향으로 움직여도 장애물에 부딪히거나 격자를 벗어나거나 궤적을 밟게 되는 경우에만 패배한다.

장애물 배치가 주어질 때, 자동차가 놓일 수 있는 모든 시작 칸에 대해 그 칸에서 시작한 게임을 누가 이기는지 판정하여라.

입력은 여러 개의 독립적인 격자로 이루어진다.

각 격자는 두 정수 N과 E(1 ≤ N, E ≤ 100)가 적힌 줄로 시작한다. N은 남북 방향의 행의 수, E는 동서 방향의 열의 수이다.

다음 N개의 줄은 격자를 나타낸다. 각 줄은 정확히 E개의 문자로 이루어진 문자열이며, i번째 줄의 j번째 문자는 좌표 (j, i)(열 j, 행 i, 모두 1부터 시작)인 칸을 뜻한다. 문자가 .이면 빈 칸이고, 대문자 X이면 장애물이 있는 칸이다.

격자 밖의 모든 위치, 즉 i ≤ 0, j ≤ 0, i > N, j > E 중 하나라도 만족하는 (j, i)는 사용할 수 없으며 장애물과 똑같이 취급한다.

격자 목록은 두 개의 0이 적힌 줄로 끝난다. 이 종료 줄은 처리하지 않는다.

각 격자에 대해 길이가 E인 문자열 N개를 출력한다.

i번째 줄의 j번째 문자는 칸 (j, i)에 대한 결과이다.

• 그 칸에서 자동차가 출발할 때 앨리스(먼저 두는 사람)가 이기면 A,
• 밥(나중에 두는 사람)이 이기면 B,
• 그 칸이 장애물이면 X를 출력한다.

서로 다른 격자의 출력 사이에는 빈 줄 하나를 넣어 구분한다.