Background

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.

Problem Description

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 Format

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.

Output Format

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.

3 3 2

NO

3 3 3

YES
RDLDRRUU
1 1

6 4 4

YES
RRRDLLLDRRRDLLLDRRRDLLL
1 1

1 1 2000

YES

1 1

Hint

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