Roller Coaster

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.

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.

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.