Description

The game is played on an unbounded board. There is a black obstacle at the center $(0,\,0)$. Not far away, there are $N$ gray blocks, each placed on a distinct cell whose coordinates are odd.

The task of the game is to glue all gray blocks together to form a given shape, as shown in Figure 1. The shape may appear anywhere on the board, but it cannot be rotated or mirrored. Figure 2 shows a valid initial state, where there is one gray block at each of $(-1,\,-1),\,(1,\,-1),\,(1,\,1)$.

Each time, the player may issue one of four move commands: up (U), down (D), left (L), or right (R), causing all gray blocks to move one cell simultaneously in the specified direction. If there is an obstacle directly in front of a block, only that block cannot move, while the other blocks still move normally. For example, starting from the state in Figure 2 and applying the commands LLUR will produce the layout shown in Figure 3. Once a situation like Figure 3 occurs, where two or more blocks are adjacent, these adjacent blocks will immediately glue together into an inseparable whole. In future moves, as long as any block in this whole has an obstacle in front of it, the entire whole cannot move, even if the other blocks are not blocked. Then, from the state in Figure 3, applying the commands URD will produce Figure 4. Since the gray blocks in Figure 4 form exactly the target shape, the game ends in victory.

This game looks simple, but when there are many blocks and the target shape is complex, the player often needs many steps to finish. Jiajia hopes to find a solution within $2000$ steps. Can you help him?

Input Format

The first line contains an integer $N$, the number of blocks.

The second line contains $N$ integer pairs $x_i,\,y_i$, where the $i$-th pair represents the initial position of the $i$-th block. The positions are listed in order from top to bottom (i.e. increasing $x$), and from left to right (i.e. increasing $y$).

The third line contains $N$ integer pairs $P_{x_i},\,P_{y_i}$, representing the relative positions of each small block in the target shape. The target is guaranteed to be a single connected whole, and the testdata always has a solution.

Output Format

The first line is the required number of steps $S$. The second line is the move sequence.

3
-1 -1 1 -1 1 1
1 1 2 1 2 2

7
LLURURD

Hint

Constraints

For $100\%$ of the testdata, $3 \leq N \leq 20$, $-9 \leq x_i,\,y_i \leq 9$, and $x_i,\,y_i$ are odd. Also, $1 \leq P_{x_i},\,P_{y_i} \leq N$.

Sample Explanation

According to the input format, in this problem the D direction is the positive direction of the $x$ axis, and the R direction is the positive direction of the $y$ axis. Therefore, the sample explanation can refer to the third paragraph of the problem description.

Translated by ChatGPT 5