题目描述

本题的可视化工具：链接（波兰语）。

Bajtazar 刚刚发现了一颗形状像环面的行星。行星表面被一个矩形网格划分为 $n$ 行和 $m$ 列。行用从 $0$ 到 $n-1$ 的整数编号，列用从 $0$ 到 $m-1$ 的整数编号，坐标为 $(x, y)$ 的格子位于第 $x$ 行和第 $y$ 列。

为了探索这颗行星，一辆太空漫游车将被送往那里，它将从坐标为 $(0, 0)$ 的格子开始工作，并按照指令序列在行星上移动。漫游车识别 4 种类型的指令，分别对应以下移动：

• $G$：从 $(x, y)$ 移动到 $((x - 1) \bmod n, y)$
• $D$：从 $(x, y)$ 移动到 $((x + 1) \bmod n, y)$
• $L$：从 $(x, y)$ 移动到 $(x, (y - 1) \bmod m)$
• $P$：从 $(x, y)$ 移动到 $(x, (y + 1) \bmod m)$

漫游车将无限循环地执行指令序列：在执行完最后一条指令后，它开始从头执行整个序列。请记住，行星的形状是环面，所以例如如果漫游车当前位于格子 $(x, 0)$ 并执行移动 $L$，它将移动到格子 $(x, m - 1)$。

Bajtazar 希望漫游车最终能访问行星上全部 $nm$ 个格子。请帮助他设计一个能保证这一点的简短（但不一定是最短）的指令序列。

注意，漫游车在行驶过程中多次访问同一个格子是允许的。

输入格式

输入的第一行也是唯一一行包含两个整数 $n$ 和 $m$ ($2 \le n, m \le 10^6$)，分别表示行星表面被划分成的行数和列数。

输出格式

输出的第一行应打印一个正整数 $k$，表示指令序列的长度。在第二行应打印一个长度为 $k$ 的由字母 $G, D, L, P$ 组成的字符串。

2 3

3
DPD

提示

样例解释

漫游车依次访问格子

$$(0,0) \xrightarrow{D} (1,0) \xrightarrow{P} (1,1) \xrightarrow{D} (0,1) \xrightarrow{D} (1,1) \xrightarrow{P} (1,2) \xrightarrow{D} (0,2) \xrightarrow{D} (1,2) \xrightarrow{P} (1,0) \xrightarrow{D} (0,0) \xrightarrow{D} \dots$$

::::align{center} ::::

样例输出是正确的，但未必是最短的。

大样例

样例 $\texttt{0a}$ 是题面中展示的样例。此外：

• $\texttt{0b}$：$n = 5, m = 4$；指令序列 $\texttt{PPPDDDLLGPGLLDDDPPP}$ 允许访问棋盘的所有格子。
• $\texttt{0c}$：$n = 1000, m = 1000$；指令序列 $(\texttt{DP})^{1\,234\,567}\texttt{GGL}$ 允许访问棋盘的所有格子。

子任务

本题采用捆绑测试。

子任务编号	限制	得分
1	$n, m \le 6$	11
2	$n, m \le 20$	20
3	$n \le 10^3, n = 2m + 3$	13
4	$n \le 10^3, m \le 20$	12
5	$n, m \le 10^3$	24
6	$n, m \le 10^4$	7
7	$n, m \le 10^5$
8	无额外限制	6

令 $k$ 表示你输出的指令序列的长度，而 $OPT$ 是最短可能的正确指令序列的长度。如果你的指令序列是正确的，那么你的解法将在该测试点获得根据以下公式计算的分数：

$$\left\lfloor \frac{100}{\sqrt{1 + k - OPT}} \right\rfloor \%$$