Robotic Vacuum Cleaner Cleaning Path

You are given a grid of size \(N \times M\) (with 1-indexed coordinates) and \(O\) obstacles placed on the grid. The robotic vacuum cleaner starts at position (\(s_x\), \(s_y\)). Your task is to compute a sequence of moves for the vacuum cleaner to clean (i.e. visit) every cell that is reachable from the starting position without hitting any obstacles.

The moves are represented by characters:

• R: move right
• D: move down
• L: move left
• U: move up

The output must be a single string that starts with an exclamation mark !, followed by the sequence of moves. The DFS (depth-first search) approach is used to explore the grid in the order: right, down, left, and up. When the DFS backtracks, the reverse move is recorded. If no move is possible (for instance, when the starting cell is isolated or the grid contains only one cell), the output should simply be !.

Note: All coordinates in the input are based on 1-indexing, but your implementation may use 0-indexing internally.

inputFormat

The input is given from standard input with the following format:

N M O
s_x s_y
x1 y1
x2 y2
... (O lines of obstacle coordinates)

Where:

• \(N\) is the number of rows in the grid.
• \(M\) is the number of columns in the grid.
• \(O\) is the number of obstacles.
• \(s_x\) and \(s_y\) are the starting coordinates of the vacuum cleaner.
• Each of the next \(O\) lines contains two integers \(x_i\) and \(y_i\) representing the coordinates of an obstacle.

outputFormat

The output should be a single string printed to standard output. It must start with an exclamation mark ! followed by a sequence of characters representing moves (using R, D, L, U). If no moves are made, output just !.

## sample

5 5 3
2 2
3 3
4 4
5 2

!URDDLULUURRDDDLLUURR