Description

Mirko has gotten tired of all books, so even though he does not like roller coasters, he decided to go to an amusement park with his friends. While his friends are having a great time, Mirko sits on a bench, waiting and thinking about possible roller coaster routes.

The amusement park can be represented as a grid with $r$ rows and $c$ columns. The roller coaster must start in the top-left cell of the grid and end in the bottom-right cell. Each cell may be visited at most once, but not all cells need to be visited. From the current cell, it can move to an adjacent cell above, below, to the left, or to the right.

Each cell has a positive integer value associated with it, representing how much fun that cell adds for the visitors. The total fun of a roller coaster is the sum of the fun values of all cells it visits. Help Mirko determine one of the most fun roller coaster routes (with maximum total fun).

Input Format

The first line contains two integers $r$ and $c$, as described above.

The next $r$ lines each contain $c$ integers (separated by spaces), indicating the fun value added by the corresponding cell.

Output Format

Output one line containing an uppercase string consisting of U, D, L, R (U means the roller coaster moves up next, D means down, L means left, R means right), describing a route that achieves the maximum total fun.

3 3
5 1 3
2 4 8
1 1 2

RRDLLDRR

2 2
2 1
3 4

DR

Hint

Constraints

• For $70\%$ of the testdata, $2 \leq r,c \leq 30$ is guaranteed.
• For $100\%$ of the testdata, $2 \leq r,c \leq 1 \times 10^3$ is guaranteed, and each character of the output string can only be U, D, L, R.

Notes

• This problem is worth $120$ points.
• Translated from COCI2010-2011 CONTEST #2 LUNAPARK. Translator:
  https://www.luogu.com.cn/user/115711

Acknowledgements

Thanks to

Additional Hint

The output may not be unique.

Translated by ChatGPT 5