CF1301D.Time to Run

Bashar was practicing for the national programming contest. Because of sitting too much in front of the computer without doing physical movements and eating a lot Bashar became much fatter. Bashar is going to quit programming after the national contest and he is going to become an actor (just like his father), so he should lose weight.

In order to lose weight, Bashar is going to run for $k$ kilometers. Bashar is going to run in a place that looks like a grid of $n$ rows and $m$ columns. In this grid there are two one-way roads of one-kilometer length between each pair of adjacent by side cells, one road is going from the first cell to the second one, and the other road is going from the second cell to the first one. So, there are exactly $(4 n m - 2n - 2m)$ roads.

Let's take, for example, $n = 3$ and $m = 4$. In this case, there are $34$ roads. It is the picture of this case (arrows describe roads):

Bashar wants to run by these rules:

• He starts at the top-left cell in the grid;
• In one move Bashar may go up (the symbol 'U'), down (the symbol 'D'), left (the symbol 'L') or right (the symbol 'R'). More formally, if he stands in the cell in the row $i$ and in the column $j$, i.e. in the cell $(i, j)$ he will move to:
  • in the case 'U' to the cell $(i-1, j)$;
  • in the case 'D' to the cell $(i+1, j)$;
  • in the case 'L' to the cell $(i, j-1)$;
  • in the case 'R' to the cell $(i, j+1)$;
• He wants to run exactly $k$ kilometers, so he wants to make exactly $k$ moves;
• Bashar can finish in any cell of the grid;
• He can't go out of the grid so at any moment of the time he should be on some cell;
• Bashar doesn't want to get bored while running so he must not visit the same road twice. But he can visit the same cell any number of times.

Bashar asks you if it is possible to run by such rules. If it is possible, you should tell him how should he run.

You should give him $a$ steps to do and since Bashar can't remember too many steps, $a$ should not exceed $3000$. In every step, you should give him an integer $f$ and a string of moves $s$ of length at most $4$ which means that he should repeat the moves in the string $s$ for $f$ times. He will perform the steps in the order you print them.

For example, if the steps are $2$ RUD, $3$ UUL then the moves he is going to move are RUD $+$ RUD $+$ UUL $+$ UUL $+$ UUL $=$ RUDRUDUULUULUUL.

Can you help him and give him a correct sequence of moves such that the total distance he will run is equal to $k$ kilometers or say, that it is impossible?

巴沙尔正在为全国编程竞赛做准备。由于长时间坐在电脑前缺乏运动，再加上暴饮暴食，他体重猛增。全国编程竞赛结束后，巴沙尔打算退出编程界，转行当一名演员（就像他父亲一样），因此他必须减重。

为了减重，巴沙尔计划跑 $k$ 千米。他将在一个由 $n$ 行 $m$ 列构成的网格状场地中跑步。该网格中，每对相邻（共享一条边）的格子之间都有两条长度为 1 千米的单向道路：一条从第一个格子指向第二个格子，另一条从第二个格子指向第一个格子。因此，道路总数恰好为 $(4 n m - 2n - 2m)$ 条。

举个例子，当 $n = 3$、$m = 4$ 时，共有 $34$ 条道路。下图展示了该情形（箭头表示道路）：

巴沙尔希望按如下规则跑步：

• 他从网格的左上角格子出发；
• 每一步，巴沙尔可向上（符号 'U'）、向下（符号 'D'）、向左（符号 'L'）或向右（符号 'R'）移动。更准确地说，若他当前位于第 $i$ 行、第 $j$ 列的格子（即格子 $(i, j)$），则：
  • 若执行 'U'，将移动至格子 $(i-1, j)$；
  • 若执行 'D'，将移动至格子 $(i+1, j)$；
  • 若执行 'L'，将移动至格子 $(i, j-1)$；
  • 若执行 'R'，将移动至格子 $(i, j+1)$；
• 他需恰好跑 $k$ 千米，即恰好进行 $k$ 步移动；
• 巴沙尔可在网格中任意格子结束跑步；
• 他不能跑出网格范围，即在任意时刻都必须位于某个格子内；
• 为避免跑步过程枯燥乏味，他不得重复经过同一条道路两次；但他可以多次访问同一格子。

巴沙尔向你求助：是否存在满足上述所有规则的跑步方案？若存在，请告诉他具体的跑步路径。

你需要给出 $a$ 个步骤，且由于巴沙尔记不住太多步骤，要求 $a \le 3000$。在每个步骤中，你需要提供一个整数 $f$ 和一个长度不超过 $4$ 的字符串 $s$，表示他应将字符串 $s$ 中的移动序列重复执行 $f$ 次。他将按你输出的顺序依次执行这些步骤。

例如，若步骤为 2 RUD、3 UUL，则他实际执行的移动序列为
RUD $+$ RUD $+$ UUL $+$ UUL $+$ UUL $=$ RUDRUDUULUULUUL。

你能帮他构造一个合法的移动序列，使得总跑步距离恰好为 $k$ 千米？若不存在这样的序列，请说明其不可能性。

The only line contains three integers $n$, $m$ and $k$ ($1 \leq n, m \leq 500$, $1 \leq k \leq 10 ^{9}$), which are the number of rows and the number of columns in the grid and the total distance Bashar wants to run.

唯一的一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 500$，$1 \leq k \leq 10 ^{9}$），分别表示网格的行数、列数以及 Bashar 想要跑的总距离。

If there is no possible way to run $k$ kilometers, print "NO" (without quotes), otherwise print "YES" (without quotes) in the first line.

If the answer is "YES", on the second line print an integer $a$ ($1 \leq a \leq 3000$) — the number of steps, then print $a$ lines describing the steps.

To describe a step, print an integer $f$ ($1 \leq f \leq 10^{9}$) and a string of moves $s$ of length at most $4$. Every character in $s$ should be 'U', 'D', 'L' or 'R'.

Bashar will start from the top-left cell. Make sure to move exactly $k$ moves without visiting the same road twice and without going outside the grid. He can finish at any cell.

We can show that if it is possible to run exactly $k$ kilometers, then it is possible to describe the path under such output constraints.

如果无法恰好跑 $k$ 千米，则在第一行输出 "NO"（不带引号）；否则在第一行输出 "YES"（不带引号）。

如果答案为 "YES"，则在第二行输出一个整数 $a$（$1 \leq a \leq 3000$），表示步数；随后输出 $a$ 行，每行描述一步。

每步的描述包含一个整数 $f$（$1 \leq f \leq 10^{9}$）和一个长度至多为 $4$ 的字符串 $s$。字符串 $s$ 中的每个字符必须为 'U'、'D'、'L' 或 'R'。

Bashar 从左上角单元格出发。请确保恰好移动 $k$ 步，且不重复经过同一条道路，也不走出网格边界。他可以在任意单元格结束。

可以证明：若恰好跑 $k$ 千米是可行的，则一定能在上述输出约束下描述出该路径。

The moves Bashar is going to move in the first example are: "RRLL".

It is not possible to run $1000000000$ kilometers in the second example because the total length of the roads is smaller and Bashar can't run the same road twice.

The moves Bashar is going to move in the third example are: "RRDDLLRR".

The moves Bashar is going to move in the fifth example are: "RRRLLLDRRRDULLLD". It is the picture of his run (the roads on this way are marked with red and numbered in the order of his running):

第一个样例中，巴沙尔的移动序列为：“RRLL”。

第二个样例中，无法跑完 $1000000000$ 千米，因为所有道路的总长度更小，且巴沙尔不能重复经过同一条道路。

第三个样例中，巴沙尔的移动序列为：“RRDDLLRR”。

第五个样例中，巴沙尔的移动序列为：“RRRLLLDRRRDULLLD”。下图展示了他跑步的路径（该路径上的道路以红色标出，并按其经过顺序编号）：