There is an $n \times m$ grid board, where both $n$ and $m$ are odd. The grid is tiled with $1 \times 2$ blocks. The blocks can be rotated and cannot overlap. There are $\frac{nm-1}{2}$ such blocks, meaning there is exactly one empty cell on the grid.

You can perform two types of operations:

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

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

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

Input

The first line contains two positive odd integers $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:

• < represents the left half of a block;
• > represents the right half of a block;
• n represents the top half of a block;
• u represents the bottom half of a block;
• o represents the empty cell.

The next $n$ lines, each containing $m$ characters, describe the target state you need to transform the grid into, using the same format.

Output

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

• L means you moved the block to the left of the empty cell;
• R means you moved the block to the right of the empty cell;
• U means you moved the block above the empty cell;
• D means you moved the block below the empty cell.

If no operations are needed, output an empty string.

Examples

Input 1

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

Output 1

URLR

Input 2

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

Output 2

RLLRLRR

Note 2

The initial state and target state are grids $A$ and $B$ in the problem figure, respectively.

Subtasks

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

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

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