2558번 - 초콜릿 먹기

형진이는 초콜릿을 좋아한다. 이차원 격자의 $(r_1, c_1)$ 에서 출발해 $(r_2, c_2)$ 에 도착하고자 한다. 모든 격자 칸에는 무한개의 초콜릿이 놓여져 있으며, $i$행 $j$열 칸에 놓인 초콜릿의 당도는 $A_{i, j}$이다. 만약 $A_{i, j} = 0$이라면 해당 칸의 초콜릿은 당을 사용하지 않은 초콜릿이 놓여있다. 형진이는 상하좌우로 인접한 칸을 이동하여 시작점에서 도착점까지 이동하며, 이동 도중에 방문한 모든 칸에서 초콜릿을 먹는다.

형진이는 처음에는 칸에 방문할 때마다 1개의 초콜릿만 먹지만, 형진이가 $i$행 $j$열 칸에서 직전에 이동했던 방향과 다른 방향으로 이동하게 될 경우, 형진이는 지쳐 이번 이동에서 도착한 칸부터, 새로운 초콜릿을 먹는 양이 영구적으로 $B_{i, j}$배 증가한다. 이 증가는 중첩되어 적용된다, 예를 들어, 한 번 지침으로서 먹는 양이 2배가 되었고, 두 번째 지침에서 먹는 양이 3배가 된다면, 기존의 2배에서 중첩되어 적용돼, 먹는 양은 6배가 된다.

여러분은 초콜릿만 보면 달려드는 형진이의 건강 상태를 걱정하고 있다. 그래서 당도 수치라는 것을 정의했다! 당도 수치는, (초콜릿의 당도 * 먹은 양)의 총합으로, 실제로 형진이가 먹은 총 당분의 양이라고 할 수 있다. 우리는 이 수치를 최소화 할 수 있는 경로를 찾아, 형진이에게 길을 알려주고자 한다. 최소화 할 수 있는 경로를 아무거나 찾아서 출력하자.

첫 번째 줄에 격자의 크기를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 500$)

두 번째 줄에 시작점의 정보를 나타내는 두 정수 $r_1$, $c_1$과, 도착점의 정보를 나타내는 두 정수 $r_2$, $c_2$가 공백을 두고 주어진다. ($1 \le r_1, c_1, r_2, c_2 \le N$)

세 번째 줄부터 $N$개의 줄에 걸쳐, 각 줄의 $i$번째 줄에는 $A$의 $i$번째 행에 해당하는 수열 $A_{i, 1}, A_{i, 2}, \dots, A_{i, N}$이 공백을 두고 주어진다. ($0 \le A_{i, j} \le 10^9$)

$N+3$ 번째 줄부터 $N$개의 줄에 걸쳐, 각 줄의 $i$번째 줄에는 $B$의 $i$번째 행에 해당하는 수열 $B_{i, 1}, B_{i, 2}, \dots, B_{i, N}$이 공백을 두고 주어진다. ($1 \le B_{i, j} \le 10^6$)

첫 번째 줄에 당도 수치를 최소화 할 수 있는 경로의 길이를 출력한다.

두 번째 줄에 상하좌우 이동을 각각 `U`, `D`, `L`, `R`으로, 공백없이 이동 경로를 출력한다.

만약 가능한 경로가 여러가지라면, 그 중 아무거나 출력한다. 단, 경로의 길이는 최대 $10^6$으로 제한되며, 이동 도중 격자를 벗어나면 안된다. 또한, 같은 칸을 여러번 방문하는 것이 답이 될 수도 있으며, 이 때에도 마찬가지로, 칸을 방문할 때마다 형진이는 다시 초콜릿을 먹음에 유의한다.