← 返回题目列表

Codeforces · 1327/C

C. 筹码游戏

中文机器翻译题面 查看原题

Petya 有一个大小为 $$$n \times m$$$ 的矩形板。最初,$$$k$$$ 筹码放置在棋盘上,第 $$$i$$$ 个筹码位于第 $$$sx_i$$$ 行和 $$$sy_i$$$ 列交叉点的单元格中。

在一次操作中,Petya 可以将所有筹码向左、向右、向下或向上移动 $$$1$$$ 格。

如果筹码在$$$(x, y)$$$单元格中,则操作后:

- 左,其坐标为 $$$(x, y - 1)$$$;
- 右,其坐标为 $$$(x, y + 1)$$$;
- 向下,其坐标为$$$(x + 1, y)$$$;
- 向上,其坐标将为$$$(x - 1, y)$$$。

如果筹码位于棋盘的墙壁附近,并且 Petya 选择的动作将其移向墙壁,则筹码将保持在当前位置。

请注意,多个芯片可以位于同一单元中。

对于每个芯片,Petya 选择它应该访问的位置。请注意,芯片不一定要处于此位置。

由于 Petya 没有很多空闲时间,因此他准备执行不超过 $$$2nm$$$ 的操作。

您必须找出 Petya 应该执行哪些操作,以便每个芯片至少访问 Petya 为其选择的位置一次。或者确定不可能在 $$$2nm$$$ 操作中执行此操作。

输入

第一行包含三个整数 $$$n, m, k$$$ ($$$1 \le n, m, k \le 200$$$) — 分别是棋盘的行数、列数和芯片数。

接下来的 $$$k$$$ 行包含两个整数,每个 $$$sx_i, sy_i$$$ ($$$ 1 \le sx_i \le n, 1 \le sy_i \le m$$$) — 第 $$$i$$$ 芯片的起始位置。

接下来的 $$$k$$$ 行包含两个整数,每个 $$$fx_i, fy_i$$$ ($$$ 1 \le fx_i \le n, 1 \le fy_i \le m$$$) — $$$i$$$ 芯片应该至少访问一次的位置。

输出

在第一行中打印操作次数,以便每个芯片至少访问 Petya 为其选择的位置一次。

在第二行输出操作序列。要表示向左、向右、向下和向上操作,请分别使用字符 $$$L、R、D、U$$$。

如果所需的序列不存在,则在单行中打印 -1。

示例

输入 #1

3 3 2
1 2
2 1
3 3
3 2

输出 #1

3
DRD

输入 #2

5 4 3
3 4
3 1
3 3
5 3
1 3
1 4

输出 #2

9
DDLUUUURR