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 , where and .

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.