Description

There is a grid board with $n$ rows and $m$ columns, where both $n$ and $m$ are odd. Some $1\times 2$ bricks are tiled on the grid. Bricks can be rotated and cannot overlap. There are $\frac{nm-1}{2}$ bricks in total, which means there is exactly one empty cell on the board.

You can perform two kinds of operations:

1. Rotate a brick that is adjacent to the empty cell (sharing a common edge) by $90^\circ$ into the empty cell.
2. Translate a brick that is adjacent to the empty cell into the empty cell.

As shown in the figure (the moved brick is in a lighter color):

Please use the two operations above to transform the given grid board into the specified target state.

Input Format

The first line contains two positive odd integers $n,m$, representing the number of rows and columns of the grid.

Then follow $n$ lines, each containing $m$ characters, describing the initial state of the grid board:

• < means this cell is the left half of a brick.
• > means this cell is the right half of a brick.
• n means this cell is the upper half of a brick.
• u means this cell is the lower half of a brick.
• o means this cell is empty.

Then follow another $n$ lines, each containing $m$ characters, describing the target state you need to transform the board into, in the same format as above.

Output Format

You need to output a string that represents your operations in order:

• L means you moved the brick on the left side of the empty cell.
• R means you moved the brick on the right side of the empty cell.
• U means you moved the brick above the empty cell.
• D means you moved the brick below the empty cell.

Of course, if there are no operations, output an empty string.

3 3
nnn
uuu
o<>
<>n
<>u
<>o

URLR

5 5
n<><>
un<>n
nuonu
u<>un
<><>u
<><>o
<><>n
<><>u
<><>n
<><>u

RLLRLRR

Hint

Constraints and Notes

The length of your output operation sequence must not exceed $8\times 10^6$.

For all testdata, $1\leq n,m\leq 2000$.

• For $10\%$ of the testdata, $n,m\leq 3$.
• For another $10\%$ of the testdata, $n,m\leq 5$.
• For another $20\%$ of the testdata, $m=3$.
• For another $20\%$ of the testdata, $n,m\leq 50$.
• For another $20\%$ of the testdata, $n,m\leq 200$.
• For the remaining $20\%$ of the testdata, there are no special restrictions.

SPJ Notes

See https://www.luogu.org/discuss/show/114298. Thanks to @M_sea for the contribution.

Translated by ChatGPT 5