26235번 - Chairs 다국어

문제

Ostap and Kisa found themselves at a chair sale. They are facing two problems. First, they must leave the sale as soon as possible, because their rival company, represented by father Theodore, is breathing down their necks; second, they must get all chairs at the sale.

The sale site is a rectangular table of $N$ rows and $M$ columns, with some of its cells occupied by chairs that need to be collected. Initially our enterpreneurs are in the top-left corner --- the cell with the coordinates $(1, 1),ドル and the exit is located in the bottom-right corner --- the cell with the coordinates $(N, M)$. A single move can transfer them from a given sell to any of adjacent by a side cells. Passing through a cell with a chair, they take the chair with them. Find a shortest path from the starting to the ending cell. Among all such paths, find one passing through all cells with chairs, or find out if such a path doesn't exist.

입력

The first line contains three integers: $N,ドル $M,ドル $K$ --- size of the table and the number of chairs, respectively (2ドル \le N, M \le 100,ドル 0ドル \le K \le 1000$).

The following $K$ lines of the input data each contain two integers: $X_i$ --- the number of the row in which the $i$-th chair is located, and $Y_i$ --- the number of the column in which the $i$-th chair is located (1ドル \le X_i \le N,ドル 1ドル \le Y_i \le M$). A single cell cannot contain multiple chairs.

출력

If collecting all chairs along any single shortest path is impossible, print a single word <<Impossible>> (without brackets) in the output file.

If such a path exists, print it as a line containing the sequence of moves, with each move coded by a single symbol according to the following:

• R --- move right;
• D --- move down;

If several solutions are possible, print the lexicographically smallest solution.

제한

힌트