Problem Description

There is a grid board with $n$ rows and $m$ columns, where both $n$ and $m$ are odd numbers. The grid is covered with some $1 \times 2$ building blocks. These blocks can be rotated and cannot overlap. There are exactly $\frac{nm-1}{2}$ blocks, which means there is only one empty cell on the grid board.

You can perform two types of operations:

1. Rotate a block adjacent to the empty cell (sharing a side) $90^\circ$ into the empty cell.
2. Move a block adjacent to the empty cell into the empty cell.

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

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

Input Format

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

The next $n$ lines, each containing $m$ characters, describe the initial state of the grid board:

• < indicates the left half of a block.
• > indicates the right half of a block.
• n indicates the upper half of a block.
• u indicates the lower half of a block.
• o indicates the empty cell.

The following $n$ lines, each containing $m$ characters, describe the target state of the grid board, using the same format as above.

Output Format

You need to output a string representing the sequence of your operations in order:

• L indicates moving the block to the left of the empty cell.
• R indicates moving the block to the right of the empty cell.
• U indicates moving the block above the empty cell.
• D indicates moving the block below the empty cell.

If there are no operations, output an empty string.

Sample Input and Output

Sample Input #1

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

Sample Output #1

URLR

Sample Input #2

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

Sample Output #2

RLLRLRR

Notes

Data Range and Notes

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

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

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

SPJ Notes

Refer to https://www.luogu.org/discuss/show/114298, thanks to @M_sea for the contribution.

见题面 Input 部分

见题面 Output 部分