题目描述

This is the hard version of this problem. The only difference between the easy and hard versions is the limit on the number of moves in your solution.

Yuki lives on a grid with $n + 1$ rows and $n$ columns. The rows are numbered $1$ to $n + 1$ from top to bottom, and the columns are numbered $1$ to $n$ from left to right. Let $(i, j)$ denote the cell at row $i$ and column $j$.

There are $n - 1$ obstacles on the grid, and their distribution satisfies the following conditions:

• There are no obstacles in row $1$ and row $n + 1$.
• For all $2 \le i \le n$, there is $\textbf{exactly}$ one obstacle in row $i$.
• For all $1 \le j \le n$, there is $\textbf{at most}$ one obstacle in column $j$.

Initially, Yuki is at $(1, 1)$. She has heard that a group of kangaroos lives in row $n + 1$, so she wants to go to row $n + 1$ to see the scenery.

To achieve her goal, Yuki can perform several moves. In each move, she chooses one of the four directions (up, down, left, right) and moves one cell in that direction. Specifically, if the target cell is outside the grid or contains an obstacle, the move is not executed.

Unfortunately, Yuki only knows the rules for the obstacle distribution, not the specific locations of the obstacles. Therefore, she wants you to help her specify the sequence of moves such that for any valid obstacle distribution, Yuki $\textbf{reaches}$ row $n + 1$ at some point (she only needs to have reached row $n + 1$ at least once; she does not need to remain there after all moves are completed).

Since Yuki is in a hurry, the number of moves in your solution must not exceed $\boldsymbol{10 \cdot n}$.

输入格式

A single line contains a positive integer $n$ $(2 \le n \le 10^3)$.

输出格式

The first line output an integer $k$ $(1 \le k \le 10 \cdot n)$, representing the number of moves in your solution.

The second line output a string $s$ of length $k$, where $s_i$ represents the direction of Yuki's $i$-th move:

• If $s_i = \texttt U$, Yuki moves up.
• If $s_i = \texttt D$, Yuki moves down.
• If $s_i = \texttt L$, Yuki moves left.
• If $s_i = \texttt R$, Yuki moves right.

2

4
DRDD

3

17
DDDUUURDDDUUURDDD

提示

For the first example:

• Let gray cells represent obstacles and white cells represent empty cells. The following image shows all possible obstacle distributions satisfying the requirements: :::align{center} :::
• For the first obstacle distribution, Yuki's path is $(1,1) \to (1,1) \to (1,2) \to (2,2) \to (3,2)$.
• For the second obstacle distribution, Yuki's path is $(1,1) \to (2,1) \to (2,1) \to (3,1) \to (3,1)$.
• For every valid obstacle distribution, Yuki reaches row $n + 1$, so the sample output is correct.

For the second example:

• Let gray cells represent obstacles and white cells represent empty cells. The following image shows all possible obstacle distributions satisfying the requirements: :::align{center} :::
• It is easy to prove that for any of these obstacle distributions, following the moves given in the sample output, Yuki will reach row $n + 1$.