P7569 "MCOI-05" Slime

On July 7, 2077, MineCraft 20.7.7 was released. This update allowed players to engrave redstone circuits onto a circuit board to perform computations. `namespace_std`, a programmer and also an MC player, wanted to build a simple slime-block tunneling machine using circuit boards in the new version. However, since `namespace_std` had not played MC for too long, he built the TNT duplicator incorrectly and got blasted into outer space. So the task of building this slime-block tunneling machine was handed over to Bookworm. Bookworm wrote the program for this tunneling machine with his liver that has durability X. However, things were not that simple.

Bookworm has a $1 \times 1$ tunneling machine and a piece of land divided into $n \times m$ cells. He plans to level this land using the tunneling machine. Formally, he needs the tunneling machine to pass through every cell **exactly once**. This seems easy. However, the implementation of the tunneling machine's program has some glitches. When the tunneling machine moves **continuously** in the same direction for **exactly** $k$ steps, it will get stuck and keep dropping TNT onto the same place. Note: placing the tunneling machine at the beginning **does not count as a move**. In other words, the tunneling machine should move $n \times m - 1$ times. Bookworm does not want to be blasted into the sky like the poor `namespace_std`, so he hopes to find a way to arrange the tunneling machine's route so that it **will not** get stuck.

Input one line with three integers $n,m,k$, representing the land's length and width, and the value $k$ in the tunneling machine program.

If there is a valid plan, output three lines: - The first line outputs a string `YES`. - The second line outputs a string of length $n \times m - 1$ consisting only of `L`, `R`, `D`, `U`, representing the direction of each move. - The third line outputs two integers $x,y$, meaning the starting point of the designed route is $(x,y)$, i.e., row $x$ and column $y$. If there are multiple possible answers, Bookworm may output **any one** of them. Otherwise, output only one line `NO`. Please note that the output may be large. **Use a fast output method**.

#### Constraints **This problem uses bundled testdata.** - Subtask 0 (1 pts): Sample. You can know whether your answer passes the `Special Judge` by submitting the output. - Subtask 1 (9 pts): $n,m,k \leq 3$. - Subtask 2 (15 pts): $n,m,k \leq 10$. - Subtask 3 (5 pts): $k \geq n$. - Subtask 4 (15 pts): $n \leq 5$. - Subtask 5 (20 pts): $k \geq 5$. - Subtask 6 (10 pts): A valid solution is guaranteed to exist. - Subtask 7 (25 pts): No special restrictions. For $100\%$ of the data, $1 \le n,m,k \le 2000$. Translated by ChatGPT 5