시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB118872.727%

문제

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.

예제 입력 1

3 3 2
1 2
3 3

예제 출력 1

RDDR

예제 입력 2

3 3 2
1 2
2 1

예제 출력 2

Impossible