34832번 - 초콜릿 먹기 스페셜 저지

문제

크기가 $N \times N$인 이차원 격자가 있다. 각 칸 $(i, j)$에는 초콜릿이 무한히 많이 놓여 있으며, 이 칸에 놓인 초콜릿 1ドル$개의 당도는 $A_{i,j}$이다. 만약 $A_{i,j} = 0$이라면 그 칸에는 당을 사용하지 않은 초콜릿이 놓여 있는 것이다.

형진이는 이 격자에서 $(r_1, c_1)$ 칸에서 출발하여 $(r_2, c_2)$ 칸까지 이동하고자 한다. 한 번 이동할 때에는 상하좌우로 변을 공유하는 인접한 칸으로만 이동할 수 있으며, 꼭짓점만을 공유하는 칸은 인접한 칸으로 취급하지 않는다. 형진이는 이동 과정에서 방문하는 모든 칸에서 초콜릿을 먹는데, 출발한 순간의 시작 칸에서도 초콜릿을 먹고, 마지막에 도착한 도착 칸에서도 초콜릿을 먹는다. 또한 같은 칸을 여러 번 방문하는 것도 가능하며, 이 경우 해당 칸을 방문할 때마다 그 칸의 초콜릿을 다시 먹는다.

처음에 형진이는 한 칸을 방문할 때마다 초콜릿을 1ドル$개씩 먹는다. 그런데 형진이가 어떤 칸 $(i, j)$에서 다음 칸으로 이동할 때, 직전에 이동했던 방향과 다른 방향으로 움직이게 되면 형진이는 지치게 된다. 이때, 이번 이동으로 도착한 칸부터 형진이가 한 칸을 방문할 때 먹는 초콜릿 개수는 영구적으로 $B_{i,j}$배가 된다. 이러한 증가는 중첩되어 곱해지며, 예를 들어 처음 방향을 바꾸어 한 번 지쳤을 때 먹는 개수가 2ドル$배가 되었다가, 이후 또 다른 칸에서 방향을 바꾸어 한 번 더 지쳐 3ドル$배가 추가로 곱해진다면, 최종적으로 형진이는 한 칸을 방문할 때마다 2ドル \times 3 = 6$배인 6ドル$개를 먹게 된다.

형진이가 실제로 섭취한 총 당분의 양을 우리는 당도 수치라고 부른다. 당도 수치는 형진이가 방문한 각 칸에 대해, 그 칸의 초콜릿 1ドル$개의 당도 $A_{i,j}$와 그 칸에서 먹은 초콜릿 개수를 곱한 값을 모두 합한 것이다. 우리는 형진이의 건강을 위해 이 당도 수치를 가능한 한 작게 만들고자 한다. 즉, 시작점 $(r_1, c_1)$에서 출발하여 도착점 $(r_2, c_2)$에 도달하는 모든 가능한 경로들 중에서, 당도 수치를 최소로 만드는 경로를 하나 찾아서 출력해야 한다. 이때 같은 칸을 여러 번 지나는 경로도 허용되며, 그때마다 해당 칸의 초콜릿을 다시 먹는다는 점에 유의한다.

입력

첫째 줄에 격자의 크기를 나타내는 정수 $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$개의 줄에 걸쳐, 각 줄의 $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$으로 제한되며, 이동 도중 격자를 벗어나면 안된다. 이때 같은 칸을 여러 번 지나는 경로도 허용되며, 그때마다 해당 칸의 초콜릿을 다시 먹는다는 점에 유의한다.

당도 수치를 최소화 할 수 있는 이동 횟수 10ドル^6$ 이하의 경로가 반드시 존재함이 보장된다.

제한

노트