Esta es la versión difícil de este problema. La única diferencia entre las versiones fácil y difícil es el límite del número de movimientos de tu solución.

Yuki vive en una cuadrícula con $n + 1$ filas y $n$ columnas. Las filas se numeran de $1$ a $n + 1$ de arriba abajo, y las columnas de $1$ a $n$ de izquierda a derecha. Sea $(i, j)$ la celda situada en la fila $i$ y la columna $j$.

Hay $n - 1$ obstáculos en la cuadrícula y su distribución satisface las siguientes condiciones:

• No hay obstáculos en las filas $1$ y $n + 1$.

• Para todo $2 \le i \le n$, hay exactamente un obstáculo en la fila $i$.

• Para todo $1 \le j \le n$, hay como máximo un obstáculo en la columna $j$.

Inicialmente, Yuki está en $(1, 1)$. Ha oído que un grupo de canguros vive en la fila $n + 1$, así que quiere ir a la fila $n + 1$ para ver el paisaje.

Para lograr su objetivo, Yuki puede realizar varios movimientos. En cada movimiento, elige una de las cuatro direcciones (arriba, abajo, izquierda, derecha) y se desplaza una celda en esa dirección. En concreto, si la celda de destino está fuera de la cuadrícula o contiene un obstáculo, el movimiento no se ejecuta.

Por desgracia, Yuki solo conoce las reglas de distribución de los obstáculos, no sus posiciones concretas. Por tanto, quiere que la ayudes a especificar una secuencia de movimientos tal que, para cualquier distribución válida de obstáculos, Yuki alcance la fila $n + 1$ en algún momento (solo necesita haber alcanzado la fila $n + 1$ al menos una vez; no necesita permanecer allí tras completar todos los movimientos).

Como Yuki tiene prisa, el número de movimientos de tu solución no debe superar $10 \cdot n$.

Entrada

Una única línea contiene un entero positivo $n$ ($2 \le n \le 10^3$).

Salida

En la primera línea, imprime un entero $k$ ($1 \le k \le 10 \cdot n$), que representa el número de movimientos de tu solución.

En la segunda línea, imprime una cadena $s$ de longitud $k$, donde $s_i$ representa la dirección del $i$-ésimo movimiento de Yuki:

• Si $s_i = \texttt{U}$, Yuki se mueve hacia arriba.

• Si $s_i = \texttt{D}$, Yuki se mueve hacia abajo.

• Si $s_i = \texttt{L}$, Yuki se mueve hacia la izquierda.

• Si $s_i = \texttt{R}$, Yuki se mueve hacia la derecha.

Ejemplos

Entrada 1

2

Salida 1

4
DRDD

Entrada 2

3

Salida 2

17
DDDUUURDDDUUURDDD

Nota

Para el primer ejemplo:

• Las celdas grises representan obstáculos y las blancas representan celdas vacías. La siguiente imagen muestra todas las posibles distribuciones de obstáculos que satisfacen los requisitos:

• Para la primera distribución de obstáculos, el recorrido de Yuki es $(1, 1) \to (1, 1) \to (1, 2) \to (2, 2) \to (3, 2)$.

• Para la segunda distribución de obstáculos, el recorrido de Yuki es $(1, 1) \to (2, 1) \to (2, 1) \to (3, 1) \to (3, 1)$.

• Para cada distribución válida de obstáculos, Yuki alcanza la fila $n + 1$, por lo que la salida del ejemplo es correcta.

Para el segundo ejemplo:

• Las celdas grises representan obstáculos y las blancas representan celdas vacías. La siguiente imagen muestra todas las posibles distribuciones de obstáculos que satisfacen los requisitos:

• Es fácil demostrar que, para cualquiera de estas distribuciones de obstáculos, siguiendo los movimientos indicados en la salida del ejemplo, Yuki alcanzará la fila $n + 1$.