Piet

Piet은 프로그래밍 언어의 하나로, 코드가 $N \times M$ 크기의 2차원 이미지로 이루어져 있는 것이 특징이다. 이름은 추상화로 유명한 네덜란드 화가 피트 몬드리안(Piet Mondrian)에서 왔다. 아래 이미지는 "Hello, world!"를 출력하는 Piet 코드이다.

Piet 프로그램에서 단위 정사각형을 코델(Codel)이라고 하며, 각 코델에는 색이 하나씩 칠해져 있다. 이는 비트맵 이미지의 픽셀에 해당하는 개념이다. 같은 색의 코델이 상하좌우로 연결된 덩어리를 블록이라고 하며, 블록이 프로그램의 최소 실행 단위가 된다. 처음 실행되는 블록은 가장 왼쪽 위 코델이 속한 블록이다. 이후에는 아래 규칙에 따라 다음 블록으로 이동하는 과정을 반복한다.

다음 블록은 DP(Direction Pointer)와 CC(Codel Chooser) 두 값으로 정한다. DP는 왼쪽, 오른쪽, 위쪽, 아래쪽 중 하나이고, CC는 왼쪽 또는 오른쪽 중 하나이다. 프로그램을 처음 시작할 때 DP는 오른쪽, CC는 왼쪽이다. 다음 블록은 아래 순서로 고른다.

• 현재 블록의 코델 중 DP 방향으로 가장 멀리 있는 코델들을 찾는다. 블록이 볼록하지 않으면 이 코델들이 서로 연속하지 않을 수 있다.
• 찾은 코델들 중 DP 방향을 바라봤을 때 CC 방향의 가장 끝에 있는 코델을 고른다. CC 방향은 DP를 기준으로 한 상대적인 방향이다. 예를 들어 DP가 아래쪽이고 CC가 오른쪽이면, 가장 왼쪽에 있는 코델이 선택된다.
• 고른 코델에서 DP 방향으로 맞닿은 코델이 속한 블록이 다음 블록이 된다.

다음 그림은 다음 블록을 고르는 과정의 예시이다.

각 칸의 글자는 색을 나타내는 값이다. 현재 블록은 A 블록이고, DP(검은 화살표)는 아래쪽, CC(회색 화살표)는 오른쪽이다. A 블록의 코델 중 DP 방향으로 가장 멀리 있는 코델은 A 블록에서 가장 아래쪽에 있는 코델이며, 그림에서 점으로 표시했다. 이 코델들 중 CC 방향의 가장 끝에 있는 코델은 테두리로 표시한 코델이다. 이 코델의 아래쪽에 맞닿은 코델(빨간색 별표)이 속한 B 블록이 다음 블록이 된다.

검은색 블록이나 이미지 경계 바깥으로는 이동할 수 없다. 다음으로 이동하려는 블록이 검은색이거나 이미지 경계를 벗어나면 아래 방법으로 진행한다.

1. CC가 왼쪽이면 오른쪽으로, 오른쪽이면 왼쪽으로 바꾼 뒤 다시 이동을 시도한다.
2. CC를 바꾼 뒤에도 이동할 수 없으면 CC는 그대로 두고 DP를 시계방향으로 회전한 뒤 다시 이동을 시도한다.
3. 시계방향으로 회전한 뒤에도 이동할 수 없으면 1번으로 돌아간다.
4. 이 과정을 반복하여 총 8가지 경우를 모두 시도했는데도 이동할 수 있는 블록을 찾지 못하면 프로그램이 종료된다.

다음 예시는 이 규칙을 적용한 경우이다. 현재 블록은 A 블록이고, DP는 위쪽, CC는 왼쪽이다. 선택된 블록이 검은색이므로 CC를 오른쪽으로 바꾸지만, 이 블록도 검은색이다. DP를 시계방향으로 회전해 오른쪽으로 바꾸고 CC를 왼쪽으로 되돌리지만, 선택된 코델에 맞닿은 블록은 이미지 밖이다. CC를 오른쪽으로 바꿔도 같은 이유로 실패한다. DP를 한 번 더 시계방향으로 회전해 아래쪽으로 바꾸면 선택된 블록은 검은색이다. 이때 CC를 오른쪽으로 바꾸면 B 블록이 선택되어 이동할 수 있다. 따라서 다음 블록은 B 블록이다. 진행 과정은 아래 다섯 그림으로 나타냈다.

Piet으로 작성된 프로그램이 주어졌을 때, 프로그램이 종료할 때까지 거치는 블록의 색을 출력하는 프로그램을 작성하시오.

참고로, 실제 Piet에는 픽셀의 색에 따라 DP나 CC가 바뀌는 연산이 있다. 이 문제에서는 위에서 설명한 규칙으로만 DP와 CC가 바뀐다고 본다.

첫 번째 줄에 자연수 $N$과 $M$이 주어진다. ($1 \le N, M \le 100$)

두 번째 줄부터 $N$줄에 걸쳐 $M$개의 글자로 이루어진 문자열이 주어진다. 각 글자는 코델의 색을 나타내는 알파벳 대문자이며, X는 검은색을 뜻한다. 종료되지 않는 프로그램은 입력되지 않으며, 가장 왼쪽 위 코델은 검은색이 아님이 보장된다.

첫 번째 줄에 프로그램이 종료될 때까지 거치는 블록의 색을 순서대로 출력한다.