Problem G
RúnaHeimur

Sliding puzzle from Wikipedia

In a sliding puzzle, an image has been divided into $n$ rows and $m$ columns. Thus in total the image has been segmented into $n \cdot m$ cells. The cells are often marked with numbers from $1$ to $n \cdot m$ from left to right. The initial state is then, for example,

1 2 3
4 5 6
7 8 9

Cell number $n \cdot m$ is then removed so there is space to slide the cells around. The cells are then moved around randomly until the image has been shuffled. The goal is then to move all the cells to their original positions so the image can be viewed as it was originally.

Up to four moves are valid in any given position.

• The move ‘U‘ means that the cell below the empty cell is moved up.

• The move ‘D‘ means that the cell above the empty cell is moved down.

• The move ‘L‘ means that the cell right of the empty cell is moved left.

• The move ‘R‘ means that the cell left of the empty cell is moved right.

If there is no such cell in any of these moves then that move is illegal for that particular position.

Input

The input consists of several lines. The first line contains two integers $n$ and $m$ ($2 \leq n, m \leq 10$), where $n$ denotes the number of rows and $m$ denotes the number of columns. Next there are $n$ lines, each containing $m$ integers. The numbers are between (and including) $1$ to $n \cdot m$ and each of these numbers appears exactly once. Furthermore the number $n \cdot m$ will always be the last number in the input.

Output

Print a single line with moves leading to a solved state. If the solution contains an illegal move it is considered incorrect. If there is no solution you should instead print impossible. You may assume that if a solution exists, there also exists a solution with at most $10\, 000$ moves. If you output a solution that uses more than $10\, 000$ moves, it will be considered incorrect.

Scoring

2 2
2 3
1 4

RDLURDLU

3 3
4 6 3
1 5 8
2 7 9

DDRRULURDLULDDRULDRULURDDLUURDLURDLURRDLLURDLURDLU

3 3
4 6 3
2 5 8
1 7 9

impossible