Cleaning Robot Moves in a Grid

In this problem, you are given a 2D grid representing a room. Each cell in the grid is one of the following characters:

• S: The starting position of a cleaning robot. There is exactly one S in the grid.
• .: A cell that can be cleaned.
• #: A wall (an obstacle) that cannot be traversed.

The robot’s task is to clean all reachable cells (i.e. all non-wall cells) by moving through them. The robot cleans a cell the moment it passes through or stops on it.

The robot moves one cell at a time in one of four directions: up, right, down, or left. When choosing its next destination among the cells that haven’t been cleaned yet, the robot always follows the shortest path and uses the following priority order for moves:

[ U,; R,; D,; L ]

Your goal is to output a single string (without spaces) denoting the concatenation of move commands that the robot takes in order to eventually clean all reachable (i.e. free) cells.

Note: Although different valid routes may exist, your output is accepted as long as every free cell in the grid is visited at least once following the above strategy.

inputFormat

The first line contains two integers (n) and (m), where (n) is the number of rows and (m) is the number of columns. Each of the following (n) lines contains a string of length (m) representing the grid. It is guaranteed that there is exactly one 'S' in the grid.

outputFormat

Output a single line containing a string that represents the sequence of moves (using only the characters U, R, D, L) the robot makes to clean all reachable cells.## sample

4 4
S...
.#..
..#.
....

RRRDDDLLULUURRDULLDDD