Bajtazar has just discovered a planet shaped like a torus. The planet's surface is divided by a rectangular grid into $n$ rows and $m$ columns. The rows are numbered with integers from $0$ to $n - 1$, the columns from $0$ to $m - 1$, and the cell with coordinates $(x, y)$ is located in row $x$ and column $y$.

To explore the planet, a space rover will be sent there, starting its work at the cell with coordinates $(0, 0)$ and moving across the planet following a sequence of instructions. The rover recognizes 4 types of instructions, which correspond to the following moves: $G$ – move from $(x, y)$ to $((x - 1) \pmod n, y)$ $D$ – move from $(x, y)$ to $((x + 1) \pmod n, y)$ $L$ – move from $(x, y)$ to $(x, (y - 1) \pmod m)$ $P$ – move from $(x, y)$ to $(x, (y + 1) \pmod m)$

The rover will execute the sequence of instructions in a loop indefinitely: after executing the last instruction, it starts executing the entire sequence from the beginning. Remember that the planet is shaped like a torus, so for example, if the rover is currently at cell $(x, 0)$ and executes a move $L$, it will move to cell $(x, m - 1)$.

Bajtazar would like the rover to eventually visit all $nm$ cells of the planet. Help him design a short (but not necessarily the shortest) sequence of instructions that guarantees this.

Note that it is permissible for the rover to visit the same cell multiple times during its journey.

Input

The first and only line of input contains two integers $n$ and $m$ ($2 \le n, m \le 10^6$) representing the number of rows and columns, respectively, into which the planet's surface is divided.

Output

In the first line of output, print a single positive integer $k$ representing the length of the instruction sequence. In the second line, print a word of length $k$ consisting of the letters $G, D, L, P$.

Examples

Input 1

2 3

Output 1

3
DPD

Note

Example explanation: The rover visits the cells in the following order: $(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$

Sample tests

Test 0a is the test from the example above. Additionally: 0b: $n = 5, m = 4$; the instruction sequence PPPDDDLLGPGLLDDDPPP allows visiting all cells on the board. 0c: $n = 1000, m = 1000$; the instruction sequence $(DP)^{1234567}GGL$ allows visiting all cells on the board.

Scoring

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Let $k$ denote the length of the instruction sequence you output, and $OPT$ be the length of the shortest possible valid instruction sequence. If your instruction sequence is valid, your solution will receive points for a given test according to the following formula:

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