Finding a Valid Path in a Grid with Obstacles

Farmer John has divided his farm into an $r \times c$ grid. Some regions of the farm are impassable. Bessie is initially at cell $(1,1)$ and is eager to have dinner at the barn located at cell $(r,c)$. It is guaranteed that starting from cell $(1,1)$ there exists at least one valid path to $(r,c)$ when moving only to the four adjacent cells (up, down, left, right). Your task is to output any one valid path with no more than $100000$ moves.

Note: This problem uses Special Judge.

inputFormat

The input begins with a line containing two integers $r$ and $c$, representing the number of rows and columns in the grid. The following $r$ lines each contain a string of $c$ characters. A cell with a dot . indicates a free cell and a # indicates an impassable cell. It is guaranteed that the cells $(1,1)$ and $(r,c)$ are free, and that there exists at least one valid path.

outputFormat

Output a string consisting of the characters U, D, L, and R. This string represents the sequence of moves Bessie takes to reach the barn. The path must be valid and contain at most $100000$ moves.

sample

3 3
...
.#.
...

DDRR