33676번 - 우주 여행 스페셜 저지

문제

우주 비행사 헤르타는 우주여행을 떠나려고 한다. 우주는 $N \times M$ 격자로 표현되며, $(r, c)$는 $r$행 $c$열에 해당하는 칸을 의미한다. 헤르타는 $(1, 1)$에서 출발하여 정확히 $L$번 이동하여 도착 지점인 $(N, M)$으로 가고자 한다.

하지만 우주에는 거대 질량 천체가 있기 때문에 시공간의 왜곡이 발생한다. 거대 질량 천체는 우주에 총 $K$개 존재하며 그중 $k$번째 거대 질량 천체는 $(r_k, c_k)$에 존재한다. 출발 지점과 도착 지점에는 거대 질량 천체가 존재하지 않으며, 한 칸에 둘 이상의 거대 질량 천체가 있는 경우는 없다. $(1 \le k \le K)$

특정 칸 $(i, j)$는 시공간 왜곡 $t_{ij}$를 가진다. $t_{ij}$는 다음과 같이 정의된다.

• $f(i, j, k)$는 $(i, j)$에서 $k$번 천체까지의 맨해튼 거리이다. 즉, $f(i, j, k) = \vert i - r_k \vert + \vert j - c_k \vert$ 이다.
• $t_{ij} = \sum\limits_{k=1}^{K} f(i, j, k)$

한 번 이동할 때마다 상, 하, 좌, 우로 인접한 칸으로만 이동할 수 있다. 즉, $(i, j)$에서 $(i - 1, j),ドル $(i + 1, j),ドル $(i, j - 1),ドル $(i, j + 1)$으로만 이동할 수 있다. 격자를 벗어나는 위치로는 이동할 수 없다.

$(a_1, b_1)$에서 $(a_2, b_2)$로 이동할 때의 이동 소요 시간은 $t_{a_1b_1} - t_{a_2b_2}$이다. 만약 소요 시간이 음수라면 $\vert t_{a_1b_1} - t_{a_2b_2} \vert$만큼 시간을 되돌아간다. 이동하려는 칸에 거대 질량 천체가 존재해도 아무런 지장 없이 이동할 수 있으며, 이미 지났던 칸으로 다시 이동할 수도 있다.

$L$번 이동한 후 도착 지점에 있으며 이동 소요 시간의 총합이 최소인 경로를 구해보자.

입력

첫 번째 줄에 양의 정수 $N,ドル $M,ドル $K,ドル $L$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $K$개의 줄에 걸쳐 거대 질량 천체의 위치가 주어진다. 그중 $k$번째 줄에는 $k$번째 거대 질량 천체의 위치 $(r_k, c_k)$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 이동 소요 시간의 총합이 최소인 경로를 나타내는 길이 $L$의 문자열 $S$를 출력한다. 문자열 $S$는 문자 U, D, L, R 로 구성되며, 이는 각각 상, 하, 좌, 우를 의미한다.

만약 그러한 경로가 여러 가지라면 그중 아무거나 하나를 출력한다. 만약 그러한 경로가 존재하지 않는다면 -1을 출력한다.

제한

• 2ドル \le N, M \le 200$
• 1ドル \le K \le NM - 2$
• 1ドル \le L \le 2\ 000$
• 1ドル \le r_k \le N$
• 1ドル \le c_k \le M$

힌트