소코반

소코반(Sokoban)은 1982년 일본에서 만들어진 게임으로, 이름은 일본어로 "창고지기"라는 뜻이다. 플레이어는 캐릭터를 움직여 창고 안의 모든 박스를 목표점 위로 옮기면 이긴다. 박스의 수와 목표점의 수는 항상 같다.

플레이어는 위, 아래, 왼쪽, 오른쪽 네 방향 중 하나로 캐릭터의 이동을 지시할 수 있으며, 규칙은 다음과 같다.

• 지시한 방향의 칸이 빈 칸(박스도 벽도 아닌 칸)이면 캐릭터가 그 칸으로 이동한다.
• 지시한 방향의 칸에 박스가 있으면 그 박스를 민다. 단, 박스가 밀려서 이동할 칸도 비어 있어야 한다.
• 지시한 방향이 벽이거나, 박스가 있지만 그 박스가 밀려 이동할 칸에 다른 박스나 벽이 있으면 캐릭터는 움직이지 않는다.

모든 박스가 목표점 위로 올라오면 게임이 끝난다. 게임이 끝난 뒤에 입력되는 키는 모두 무시된다.

소코반의 해가 존재하는지 판정하는 문제는 매우 어렵지만(NP-hard이자 PSPACE-complete), 여기서는 주어진 키 입력을 그대로 시뮬레이션하기만 하면 된다.

게임판의 각 칸은 다음 문자로 나타낸다.

플레이어가 누른 키가 순서대로 주어질 때, 게임이 어떻게 진행되는지를 출력하는 프로그램을 작성하시오. 아래 첫 번째 예제가 이 규칙을 보여 준다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 게임판의 행의 수 $R$과 열의 수 $C$가 주어진다. ($4 \le R \le 15$, $4 \le C \le 15$) 이어지는 $R$개의 줄에는 현재 게임판의 상태가 주어지며, 각 줄은 정확히 $C$개의 문자로 이루어진다. 그 다음 줄에는 플레이어가 누른 키가 순서대로 주어지며, 길이는 최대 50이다. 위, 아래, 왼쪽, 오른쪽은 각각 U, D, L, R로 나타낸다.

입력의 마지막 줄에는 0 0이 주어진다.

주어지는 모든 게임판에는 캐릭터가 정확히 한 명 있고, 박스의 수와 목표점의 수가 같다. 또한 목표점 위에 있지 않은 박스가 적어도 하나 있으며, 게임판의 가장 바깥쪽 칸은 모두 벽이다.

각 게임마다 먼저 Game k: complete 또는 Game k: incomplete를 출력한다. 여기서 $k$는 게임 번호로 1부터 시작해 순서대로 증가하며, 모든 박스를 목표점으로 옮겨 게임이 끝났으면 complete를, 그렇지 않으면 incomplete를 출력한다. 그다음 $R$개의 줄에 게임의 최종 상태를 출력한다.