Maximum Entertainment Roller Coaster

Mirko is tired of all books and, despite his dislike for roller coasters, decides to join his friends at an amusement park. However, while his friends enjoy the rides, Mirko sits on a bench pondering the possible routes of a roller coaster.

The park is represented as a grid with r rows and c columns. The roller coaster must start at the top‐left cell and finish at the bottom‐right cell. From any cell, you may move to an adjacent cell (up, down, left, or right) and each cell may be visited at most once (it is not required to visit every cell).

Every cell has an associated positive integer value that represents the additional entertainment it provides. The total entertainment score of a roller coaster route is the sum of the values of all visited cells. Help Mirko determine one route that maximizes the total entertainment value.

If you need to include any formulas, please use LaTeX format, for example: The total score is given by \(\sum_{(i,j)\in P}a_{ij}\).

inputFormat

The first line contains two integers r and c, separated by a space. Each of the next r lines contains c positive integers. These represent the entertainment values for the corresponding cells in the grid.

outputFormat

Output a string consisting of the characters R (right), L (left), U (up), and D (down) that indicates one valid route from the top‐left corner to the bottom‐right corner. This route should have the maximum total entertainment value. If multiple routes yield the same maximum total, output any one of them.

sample

3 3
1 2 3
4 5 6
7 8 9

RRDLLRR