巴沙尔正在为全国编程大赛练习。由于坐在电脑前太多,没有做任何身体动作,而且吃得很多,巴沙尔变得胖了很多。巴沙尔将在全国比赛后退出节目,他将成为一名演员(就像他的父亲一样),所以他应该减肥。
为了减肥,巴沙尔准备跑步$$$k$$$公里。 Bashar 将在一个看起来像 $$$n$$$ 行和 $$$m$$$ 列的网格的地方运行。在该网格中,每对相邻的单元格之间有两条长度为一公里的单向道路,一条道路从第一个单元格到第二个单元格,另一条道路从第二个单元格到第一个单元格。因此,总共有 $$$(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$$$ 要做的步骤,并且由于Bashar 记不住太多步骤,所以$$$a$$$ 不应超过$$$3000$$$。在每一步中,你应该给他一个整数 $$$f$$$ 和一个长度最多 $$$4$$$ 的移动字符串 $$$s$$$,这意味着他应该重复字符串 $$$s$$$ 中的移动 $$$f$$$ 次。他将按照您打印的顺序执行这些步骤。
例如,如果步骤是$$$2$$$ RUD、$$$3$$$ UUL,那么他要移动的动作是 RUD $$$+$$$ RUD $$$+$$$ UUL $$$+$$$ UUL $$$+$$$ UUL $$$=$$$ RUDRUDUULUULUUL。
你能帮助他并给他一个正确的移动顺序,使他跑的总距离等于 $$$k$$$ 公里,或者说这是不可能的?
输入
唯一一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 500$$$, $$$1 \leq k \leq 10 ^{9}$$$),分别是网格中的行数和列数以及巴沙尔想要运行的总距离。
输出
如果没有可能跑 $$$k$$$ 公里,则在第一行打印“NO”(不带引号),否则打印“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$$$ 公里,那么就有可能在这种输出约束下描述路径。
示例
输入 #1
3 3 4
输出 #1
YES 2 2 R 2 L
输入 #2
3 3 1000000000
输出 #2
NO
输入 #3
3 3 8
输出 #3
YES 3 2 R 2 D 1 LLRR
输入#4
4 4 9
输出#4
YES 1 3 RLD
输入 #5
3 4 16
输出 #5
YES 8 3 R 3 L 1 D 3 R 1 D 1 U 3 L 1 D
注意
巴沙尔在第一个例子中要走的棋是:“RRLL”。
在第二个示例中不可能跑 $$$1000000000$$$ 公里,因为道路总长度较小,Bashar 不能在同一条道路上跑两次。
巴沙尔在第三个例子中要走的棋是:“RRDDLLRR”。
巴沙尔在第五个例子中要走的棋是:“RRRLLLDRRRDULLLD”。是他跑步的照片(这条路用红色标出,并按照他跑步的顺序编号):