Roller Coaster

Time limit1sMemory limit256 MB

Summary

Find a self-avoiding path from top-left to bottom-right on a grid up to 1000x1000 that maximizes the sum of visited cells' joy values.

Level: Hard9 of 10
Topics: Dynamic programming, Graph, Greedy
Solved: No attempts yet

Problem

An amusement park operator has obtained a rectangular site for a new roller coaster. The site is divided into a grid with R rows and C columns.

The roller coaster must start in the upper-left cell and finish in the lower-right cell. Each move goes from the current cell to one of its up, down, left, or right neighboring cells. A cell may be visited at most once, and the route does not have to visit every cell.

Each cell contains the amount of joy a rider gets when the roller coaster passes through that cell. The total joy is the sum of the joy values of all visited cells.

Find a route for the roller coaster that maximizes the total joy.

Input

The first line contains the number of rows R and the number of columns C. (2 <= R, C <= 1000)

The next R lines contain the joy values of the cells. Each value is a positive integer less than 1000.

Output

Print one route from the upper-left cell to the lower-right cell on the first line.

Print U for a move up, R for a move right, L for a move left, and D for a move down.

If there are multiple routes with maximum total joy, print any one of them.

Examples2

Example 1
Input
```
3 3
5 1 3
2 4 8
1 1 2
```
Expected output
```
RRDLLDRR
```
Example 2
Input
```
2 2
2 1
3 4
```
Expected output
```
DR
```