배찌의 대청소

배찌는 가을을 맞아 대청소를 하려고 한다. 배찌의 집은 세로 $N$칸, 가로 $M$칸으로 이루어진 격자로 나타낼 수 있으며, 빈칸, 장애물, 블럭으로 이루어져 있다. 배찌는 초기에 빈칸 중 하나에 서 있으며 다음과 같은 $5$가지 종류의 행동을 반복할 수 있다.

• 위로 이동
• 아래로 이동
• 왼쪽으로 이동
• 오른쪽으로 이동
• 물폭탄을 터트림

이동의 경우 상하좌우 중 한 방향으로 인접해있는 빈칸으로 이동하는 것이며, 장애물 또는 블럭이 있는 칸으로 이동하거나 집 밖으로 이동하는 것은 불가능하다.

물폭탄을 터트리는 경우 즉시 물줄기가 상하좌우 네 방향으로 최대 $K$칸 나아간다. 네 방향의 물줄기는 서로 독립적이며, 각 물줄기는 처음으로 장애물, 블럭, 혹은 집 끝에 도달한 경우 멈춘다. 만약 물줄기를 멈춘 것이 블럭이라면 해당 블럭은 파괴된다. 따라서 물줄기가 파괴한 블럭과 배찌와의 거리는 최대 $K$칸이고, 한 번 물폭탄을 터트려서 파괴할 수 있는 블럭은 최대 $4$개이다.

배찌는 집에 있는 블럭들을 되도록 많이 파괴하는 것이 목표이며, 블럭을 모두 파괴하는 방법이 여러 가지일 경우 행동을 되도록 적게 쓰는 것이 목표이다.

배찌의 대청소를 도와주자!

입력 형식

첫 번째 줄에 정수 $N$, $M$, $K$가 공백을 사이에 두고 주어진다. ($1 \le N, M, K \le 100$)

두 번째 줄부터 $N$개의 줄에 걸쳐 집의 상태를 나타내는 길이 $M$의 문자열이 주어진다.

각 줄에 주어지는 문자열에 등장하는 문자와 그 의미는 다음과 같다.

• .: 빈칸
• #: 장애물
• @: 블럭
• *: 초기에 배찌가 있는 빈칸

단, 입력에 *은 정확히 한 개, @은 한 개 이상 존재하며, 배찌가 블럭을 모두 파괴할 수 있는 입력만 주어진다.

출력 형식

배찌의 행동을 나타내는 U, D, L, R, B로 이루어진 길이 $1$ 이상 $100\,000$ 이하의 문자열을 출력한다.

각 문자의 의미는 다음과 같다.

• U: 위로 이동
• D: 아래로 이동
• L: 왼쪽으로 이동
• R: 오른쪽으로 이동
• B: 물폭탄을 터트림

단, 이동의 경우 해당 방향으로 이동이 불가능한 경우, 즉 해당 방향에 장애물 또는 블럭이 있거나 집 바깥인 경우 제자리에 머무른다.

예제

3 4 2
*@.@
##..
@@@#

BRRBDDBB

예제 설명

이 출력은 최소한의 행동으로 모든 블럭을 파괴하는 출력이다. 단, 블럭을 다 파괴하지 못하거나 너무 긴 출력도 경우에 따라 부분점수를 얻을 수 있다. 정확한 부분점수의 계산 공식은 아래의 "채점 방식"을 참고하라.

채점 방식

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

이 문제의 총점은 모든 테스트케이스의 점수의 합으로 계산된다. 각 테스트케이스의 점수를 계산하는 방법은 다음과 같다.

• $X$: 참가자의 테스트케이스 점수
• $V$: 집의 초기 블럭 개수
• $B$: 배찌가 파괴한 블럭 개수
• $L$: 출력 길이
• $S$: 테스트케이스 만점
• $P, Q$: 테스트케이스별 상수

1. $B < V$ 인 경우:
   $$X = S \times \left(0.2 \times \frac{B}{V}\right)$$
2. $B = V$, $Q \le L$ 인 경우:
   $$X = S \times 0.2$$
3. $B = V$, $P < L < Q$ 인 경우:
   $$X = S \times \left(0.2 + 0.8 \times \frac{Q - L}{Q - P}\right)$$
4. $B = V$, $L \le P$ 인 경우:
   $$X = S$$

이때 $X$는 $0.1$ 단위로 버림 된다. 각 테스트케이스의 $S$, $P$, $Q$ 값은 다음과 같다.

각 테스트케이스에서 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설