该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$Bob$ 控制着一个机器人，行走在一个 $h$ 行和 $w$ 列的网格上。

设 $(i,j)$ 表示从上往下第 $i$ 行和从左往下第 $j$ 列的单元格。网格上有 $n$ 个硬币，第 $i$ 个硬币在单元格 $(r_i,c_i)$ 上。

机器人从单元格 $(1,1)$ 开始，反复向下 ('D') 或向右 ('R') 移动一个单元格，最终到达单元格 $(h,w)$ ，当机器人移动到一个有硬币的格子，会自动捡起格子中的硬币。

$Bob$ 想完成两个任务：求机器人最多能捡多少硬币？给出一种移动方案，使得机器人移动后捡到最多的硬币（如果有多种方案，输出任意一种都正确）。

任务类型 1 ：只需要求最多的硬币数。

任务类型 2 ：求最多的硬币数和输出一种方案。

输入格式

第一行，$3$ 个整数 $h,w,n$

接下来 $n$ 行,表示硬币所在行和列，即 $(r_i,c_i)$

接下来一行，一个整数 $1$ 或 $2$ ，表示询问类型。

如果输入 1 表示只需要求第一问，即只求机器人最多能捡多少硬币；

如果输入 2 表示需要求两问，即求最多硬币数和输出一种移动方案。

输出格式

两种情况

如果只求第一问，即类型1 , 输出一行 ：一个整数表示最多能捡到的硬币数量。

如果求两问，即类型2，需要输出两行 ：第一行一个整数表示最多捡到硬币的数量，第二行一个由 'R' 和 'D' 构成的长度为 $h+w-2$ 的字符串，表示机器人移动方法。

3 4 4
3 3
2 1
2 3
1 4
2

3
DRRDR

样例1解释

行走过程如下：

如上图所示，通过移动 $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$ ，您可以在 $(2,1),(2,3),(3,3)$ 处拾取三枚硬币。

2 2 2
2 1
1 2
1

1

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1
2

5
DRRRRRRRRDDDDDRRDRDDRRR

数据规模与约定

所有数据满足：

• $2\leq H,W \leq 2\times 10^5$
• $1\leq N \leq \min(HW-2, 2\times 10^5)$
• $1\leq R_i \leq H$
• $1\leq C_i \leq W$
• $(R_i,C_i)\neq (1,1)$
• $(R_i,C_i)\neq (H,W)$
• $(R_i,C_i)$ 成对不同。
• 所有输入值都是整数。