Miku's Snake Game#12446
Miku is playing the classic game Snake.
The game is played on a rectangular board with rows and columns. The snake consists of several consecutive cells of the board. On each step, the snake's head moves to one of the four neighboring cells: up, down, left, or right. After that, each other segment of the snake follows the segment that was directly in front of it.
The snake cannot leave the board, and no two segments of its body may occupy the same cell.
Miku wants to place a snake of maximum possible length on the board so that after it starts moving, it can move forever.
You need to output any such placement.
The placement should be described as a table with rows and columns. Each cell must contain one of five symbols:
"L" — this cell belongs to the snake, and the next segment of the snake is located in the neighboring cell to the left;
"R" — this cell belongs to the snake, and the next segment of the snake is located in the neighboring cell to the right;
"U" — this cell belongs to the snake, and the next segment of the snake is located in the neighboring cell above;
"D" — this cell belongs to the snake, and the next segment of the snake is located in the neighboring cell below;
"." — this cell does not belong to the snake.
In other words, if you start from any snake cell and repeatedly move according to the symbol written in the current cell, you must visit all snake cells and return to the starting cell. Thanks to this, the snake will be able to move forever.
In addition, the snake cannot immediately return to the cell it just came from. Formally, there must not exist two neighboring snake cells and such that the symbol in cell points to cell , and the symbol in cell points back to cell .
For example, a cell with symbol "D" located directly above a cell with symbol "U" is forbidden. Likewise, a cell with symbol "R" located directly to the left of a cell with symbol "L" is forbidden.
If there are multiple correct placements of maximum length, output any of them.
The single line contains two integers and (2 \le n, m \le 1000) — the dimensions of the board.
In the first line, output one integer — the maximum length of a snake that can be placed on the board so that it can move forever.
In the next lines, output characters in each — the description of the snake placement.
The number of non-empty cells, that is, cells with symbols "L", "R", "U", or "D", must be equal to .
Example 1
Example 2
In the first example, the board has size 3 \times 5. Since both dimensions are odd, the snake cannot occupy all cells. One optimal placement has length .
If you start from cell and follow the arrows, the snake will visit all occupied cells and return to cell , so it can move forever.
In the second example, the board has size 4 \times 4. In this case, the snake can occupy all cells.
Subtask ( points): and are even.
Subtask ( points): at least one of and is even.
Subtask ( points): No additional constraints.