Magic Path

Each cell of an $N\times M$ grid is either inhabited or uninhabited. The rows are numbered $0,1,\cdots,N-1$ from top to bottom, and the columns are numbered $0,1,\cdots,M-1$ from left to right. A grid point is represented by coordinates $(i,j)$, where $0\le i\le N$ and $0\le j\le M$.

You must output a path along the grid lines from $(0,0)$ to $(N,M)$. In one move, you may move to a vertically or horizontally adjacent grid point, and you may not leave the grid.

For each inhabited cell, a cost of $1$ is incurred if the path visits at least one of the cell's four corners. Even if the path visits multiple corners of the same cell, that cell's cost is counted only once. The cost of a path is the number of cells for which a cost is incurred.

See the Scoring section for the exact scoring rules.

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the following two lines.

$C\ K$ $S$

$S$ must be a string of length $K$, and each character must be one of U, D, L, and R. These characters indicate a move by one grid point upward, downward, leftward, and rightward, respectively.

The movement sequence represented by $S$ must start at , remain inside the grid at all times, and end at .

• $1\le T\le 100\,000$.
• $1\le N,M\le 1\,000$.
• The sum of over all test cases is at most .

Each subtask is scored independently. The approximation-ratio criteria below apply equally to every subtask.

For each test case, let $o$ be the optimal cost and let $a$ be the actual cost of the valid path printed by the contestant. Define the approximation ratio $c$ as follows.