CF1301D Time to Run

Bashar 正在为全国编程竞赛做准备。由于长时间坐在电脑前且缺乏运动，加上吃得太多，Bashar 变得非常胖。Bashar 打算在全国竞赛后退出编程，转行成为演员（就像他的父亲一样），所以他需要减肥。 为了减肥，Bashar 打算跑 $k$ 公里。他将在一个看起来像 $n$ 行 $m$ 列的网格中跑步。在这个网格中，每一对相邻的格子之间都有两条单向长度为一公里的道路，一条从第一个格子到第二个格子，另一条从第二个格子到第一个格子。因此，总共有 $4 n m - 2n - 2m$ 条道路。 例如，若 $n = 3$，$m = 4$，则有 $34$ 条道路。下图展示了这种情况（箭头表示道路方向）：  Bashar 跑步的规则如下： - 他从网格的左上角格子出发； - 每一步，Bashar 可以向上（用符号 '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$ 步； - Bashar 可以在网格的任意一个格子结束； - 他不能走出网格，因此任何时刻都必须在某个格子内； - Bashar 不希望感到无聊，因此同一条道路不能重复经过。但同一个格子可以经过任意多次。 Bashar 想知道是否有可能按照这些规则完成跑步。如果可能，你需要告诉他具体的跑步方案。 你需要给出 $a$ 个步骤。由于 Bashar 记不住太多步骤，$a$ 不能超过 $3000$。每一步，你需要给出一个整数 $f$ 和一个长度不超过 $4$ 的移动字符串 $s$，表示他需要将字符串 $s$ 的移动方式重复 $f$ 次。他会按照你输出的顺序依次执行这些步骤。 例如，如果步骤为 $2$ RUD，$3$ UUL，则他将依次执行的移动为 RUD $+$ RUD $+$ UUL $+$ UUL $+$ UUL，即 RUDRUDUULUULUUL。 你能帮他给出一个满足条件的移动序列，使得总路程恰好为 $k$ 公里，或者说明这是不可能的吗？ 你需要保证 Bashar 从左上角格子出发，恰好走 $k$ 步，且不重复经过同一条道路，也不走出网格。他可以在任意格子结束。 可以证明，如果存在恰好跑 $k$ 公里的方案，则一定可以在上述输出限制下描述出路径。

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

如果不存在满足条件的方案，输出一行 "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$ 步，且不重复经过同一条道路，也不走出网格。他可以在任意格子结束。

第一个样例中 Bashar 的移动为："RRLL"。 第二个样例中无法跑 $1000000000$ 公里，因为道路总长度不足，且 Bashar 不能重复经过同一条道路。 第三个样例中 Bashar 的移动为："RRDDLLRR"。 第五个样例中 Bashar 的移动为："RRRLLLDRRRDULLLD"。下图展示了他的跑步路径（红色标记的道路按跑步顺序编号）：  由 ChatGPT 4.1 翻译