이어서 터뜨리기 -- 블록 게임

로버트는 최근 인터넷에서 'Link and Pop'의 최신 버전 게임을 발견했다. 규칙은 매우 간단하다. 처음에 $n \times m$ 크기의 판이 $n \times m$개의 블록으로 가득 차 있다. 각 블록에는 기호가 하나 적혀 있다. 해야 할 일은, 같은 기호가 적힌 블록 두 개를 최대 세 개의 수평 또는 수직 직선 구간으로 이루어진 선으로 이을 수 있는 쌍을 찾는 것이다. 단, 이 선은 판 위의 다른 블록을 지나갈 수 없다(그림 1은 연결 가능한 몇 가지 예시이며, 일부 블록은 이미 판에서 제거된 상태임에 유의하라).

그림 1

이러한 쌍을 찾으면 두 블록을 함께 터뜨려(제거) 없앤다. 그 뒤에는 아래에서 설명하는 규칙에 따라 일부 블록이 새 위치로 이동할 수 있다. 그런 다음 다시 다음 쌍을 찾는다. 판에 블록이 하나도 남지 않거나 더 이상 그런 쌍을 찾을 수 없을 때까지 게임이 계속된다.

블록의 이동 규칙은 다음과 같다. 먼저 각 블록은 '위', '아래', '왼쪽', '오른쪽', '정지' 중 하나인 고정된 이동 속성을 가진다. 한 쌍이 제거되면 블록들을 하나씩 확인하며, 자신의 이동 속성 방향으로 이동할 수 있는지 본다. 가장 윗줄의 블록을 먼저 확인하고, 같은 줄에서는 왼쪽 블록을 먼저 확인한다. 이동 속성 방향으로 인접한 칸이 비어 있으면 그 블록은 즉시 그 칸으로 이동한다. 어떤 블록도 판의 경계를 넘어갈 수는 없다. 물론 '정지' 속성의 블록은 항상 제자리에 머문다. 모든 블록을 한 번씩 확인하는 것을 한 '확인 회차'라 하며, 한 회차가 끝나면 다음 회차를 시작한다. 이는 더 이상 이동할 수 있는 블록이 없을 때까지 반복된다. 한 회차 안에서 각 블록은 한 번만 확인·이동된다. 이번 회차에 이미 이동한 블록을 새 위치에서 다시 확인·이동해서는 안 된다.

로버트는 이 게임이 매우 흥미롭다고 느꼈다. 그러나 얼마간 플레이한 뒤, 판의 크기가 꽤 클 때는 쌍을 찾기가 매우 어렵다는 것을 알게 되었다. 게다가 더 이상 터뜨릴 블록이 없어 게임이 끝나 버리는 경우도 잦았다. 로버트는 모든 블록을 터뜨리지 못한 것이 자기 잘못은 아니라고 느꼈다. 단지 블록들이 처음에 무작위로 놓이면 게임을 끝내지 못할 가능성이 크다는 것이다. 하지만 이를 게임을 여러 번 해서 확인하려면 시간이 너무 오래 걸린다. 그래서 로버트는 자신의 플레이 방식을 시뮬레이션하여 게임을 끝낼 수 있는지 확인하는 프로그램을 대신 작성해 달라고 부탁했다.

이런 프로그램을 만들 수 있도록, 로버트는 자신이 쌍을 고르는 규칙을 다음과 같이 정리했다. 먼저, 하나의 직선 구간으로 이을 수 있는 쌍이 있으면 그것을 가장 먼저 찾아 터뜨린다(이런 쌍은 찾기 쉽기 때문이다). 그런 쌍이 없으면 두 개의 직선 구간으로 이을 수 있는 쌍을 찾아 터뜨린다. 그마저도 없으면 세 개의 직선 구간으로 이을 수 있는 쌍을 찾아 터뜨린다. 같은 개수의 직선 구간으로 이을 수 있는 쌍이 여러 개라면, 가장 윗줄(같은 줄이면 가장 왼쪽)에 위치한 블록을 포함하는 쌍을 먼저 고른다. 이 규칙으로도 동점이 풀리지 않으면(가장 위·왼쪽 블록을 여러 쌍이 공유할 수 있다), 각 쌍의 나머지 블록을 같은 규칙으로 비교한다. 그림 2는 위 규칙을 따르는 미니 게임의 진행 과정을 보여 준다.

그림 2

입력은 30개 이하의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 판의 크기인 두 정수 $n$, $m$ ($1 \le n, m \le 30$)이 주어진다. 이 줄 다음에는 $n$개의 줄이 이어진다. 각 줄에는 하나의 공백으로 구분된 $m$개의 문자열이 있으며, 각 문자열은 초기 배치에서 하나의 블록을 나타낸다. 각 문자열은 항상 두 개의 대문자로 이루어진다. 첫 글자는 블록의 기호이고, 둘째 글자는 항상 'U', 'D', 'L', 'R', 'S' 중 하나로 블록의 이동 속성을 나타낸다. 각각 위, 아래, 왼쪽, 오른쪽, 정지를 의미한다. 테스트 케이스 사이에는 빈 줄이 없다. 입력은 두 개의 0으로 이루어진 줄 '0 0'으로 끝난다.

각 테스트 케이스마다 먼저 테스트 케이스 번호를 Case k 형식으로 출력한다. 이 줄 다음에는 판의 최종 상태를 $n$개의 줄로 출력하며, 각 줄은 $m$개의 문자로 이루어진다. 어떤 위치에 블록이 있으면 그 블록의 기호를 출력하고, 블록이 없으면 마침표(.)를 출력한다. 테스트 케이스 사이에는 빈 줄을 출력하지 않는다.