K-좀비

우니는 놀이공원에 있는 좀비 어트랙션에 들어가게 되었다. 좀비 어트랙션은 $N$ 개 행과 $M$ 개 열의 격자로 이루어져 있다. 우니는 처음에 격자의 왼쪽 위인 $1$ 번째 행, $1$ 번째 열 격자 칸에서 시작해서, 격자의 오른쪽 아래인 $N$ 번째 행, $M$ 번째 열 격자 칸까지 가려고 한다. 우니는 현재 있는 칸에서 위, 아래, 왼쪽, 오른쪽 칸 중 하나로 움직일 수 있다. 우니는 좀비 때문에 겁에 질려있기 때문에, 움직이지 않고 가만히 있을 수는 없다. 한 칸을 움직이는 데는 $1$의 시간이 걸리며, 처음에는 시각 $0$으로 시작한다. 즉, 현재 시각은 지금까지 움직인 횟수와 같다.

좀비 어트랙션의 각 격자 칸은 다음 중 하나이다.

• 빈칸: 우니가 자유롭게 오갈 수 있는 격자 칸이다.
• 벽: 우니가 오갈 수 없는 격자 칸이다.
• $K$-좀비: 주기가 $K$인 좀비이다. ($2 \le K \le 9$)
  • 우니는 $K$-좀비가 있는 격자 칸으로 오갈 수 없다.
  • 시각이 $K$의 배수가 아니면, $K$-좀비가 있는 격자 칸에 상하좌우로 인접한 칸에는 갈 수 없다.

우니가 오른쪽 아래 칸으로 움직여서 좀비 어트랙션에서 빠져나오는 것을 도와주자!

입력 형식

첫 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 25$)

다음 $N$ 개의 줄에는 길이 $M$의 문자열이 주어진다. 이중 $i$ 번째 줄의 $j$ 번째 문자는 다음을 의미한다.

• .: $i$ 번째 행, $j$ 번째 열에 해당하는 격자 칸은 빈칸이다.
• #: $i$ 번째 행, $j$ 번째 열에 해당하는 격자 칸은 벽이다.
• 2~9: $i$ 번째 행, $j$ 번째 열에 해당하는 격자 칸은 주기 $K$가 입력으로 주어진 문자에 해당하는 $K$-좀비이다.

출력 형식

문제의 조건을 만족하면서 우니가 오른쪽 아래 칸으로 가는 이동 커맨드를 나타내는 문자열을 출력하여라. 문자열의 길이는 $100\, 000$ 이하이고, 각 문자는 UDLR 중 하나로 이루어져 있어야 한다. 가능한 답이 여럿일 경우, 아무 것이나 하나 출력한다. 문자열의 길이가 가능한 것 중 최소일 필요는 없다.

문자열의 $i$ 번째 문자는 다음을 의미한다.

• U: 시각 $i-1$에서 우니가 한 칸 위로 움직였다.
• D: 시각 $i-1$에서 우니가 한 칸 아래로 움직였다.
• L: 시각 $i-1$에서 우니가 한 칸 왼쪽으로 움직였다.
• R: 시각 $i-1$에서 우니가 한 칸 오른쪽으로 움직였다.

우니가 이동하는 동안 움직일 수 없는 칸으로 가서는 안 되고, 최종적으로 오른쪽 아래 칸에 있어야 한다.

주어지는 모든 입력에서, 우니가 항상 오른쪽 아래 격자 칸으로 이동해서 좀비 어트랙션을 빠져나가는 길이 $100\, 000$ 이하의 이동 커맨드를 나타내는 문자열이 있음이 보장된다.

예제

4 4
....
...3
...#
....

RRDDDR

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

해설