Это сложная версия задачи. Единственное отличие между простой и сложной версиями — ограничение на количество ходов в вашем решении.

Yuki живёт на сетке из $n + 1$ строк и $n$ столбцов. Строки пронумерованы от $1$ до $n + 1$ сверху вниз, а столбцы — от $1$ до $n$ слева направо. Обозначим через $(i, j)$ клетку в строке $i$ и столбце $j$.

На сетке расположены $n - 1$ препятствий, и их расположение удовлетворяет следующим условиям:

• В строках $1$ и $n + 1$ нет препятствий.

• Для всех $2 \le i \le n$ в строке $i$ находится ровно одно препятствие.

• Для всех $1 \le j \le n$ в столбце $j$ находится не более одного препятствия.

Изначально Yuki находится в $(1, 1)$. Она слышала, что в строке $n + 1$ живёт группа кенгуру, поэтому хочет отправиться в строку $n + 1$ полюбоваться пейзажем.

Для достижения цели Yuki может сделать несколько ходов. При каждом ходе она выбирает одно из четырёх направлений (вверх, вниз, влево, вправо) и перемещается на одну клетку в этом направлении. При этом, если целевая клетка находится за пределами сетки или содержит препятствие, ход не выполняется.

К сожалению, Yuki знает лишь правила расположения препятствий, но не их точные позиции. Поэтому она просит вас помочь ей задать последовательность ходов, такую что при любом допустимом расположении препятствий Yuki в какой-то момент достигнет строки $n + 1$ (ей достаточно побывать в строке $n + 1$ хотя бы один раз; оставаться там после выполнения всех ходов не требуется).

Поскольку Yuki торопится, количество ходов в вашем решении не должно превышать $10 \cdot n$.

Входные данные

В единственной строке задано положительное целое число $n$ ($2 \le n \le 10^3$).

Выходные данные

В первой строке выведите целое число $k$ ($1 \le k \le 10 \cdot n$), обозначающее количество ходов в вашем решении.

Во второй строке выведите строку $s$ длины $k$, где $s_i$ обозначает направление $i$-го хода Yuki:

• Если $s_i = \texttt{U}$, Yuki идёт вверх.

• Если $s_i = \texttt{D}$, Yuki идёт вниз.

• Если $s_i = \texttt{L}$, Yuki идёт влево.

• Если $s_i = \texttt{R}$, Yuki идёт вправо.

Примеры

Входные данные 1

2

Выходные данные 1

4
DRDD

Входные данные 2

3

Выходные данные 2

17
DDDUUURDDDUUURDDD

Примечание

Для первого примера:

• Серые клетки обозначают препятствия, а белые — пустые клетки. На следующем рисунке показаны все возможные расположения препятствий, удовлетворяющие требованиям:

• Для первого расположения препятствий путь Yuki имеет вид $(1, 1) \to (1, 1) \to (1, 2) \to (2, 2) \to (3, 2)$.

• Для второго расположения препятствий путь Yuki имеет вид $(1, 1) \to (2, 1) \to (2, 1) \to (3, 1) \to (3, 1)$.

• При каждом допустимом расположении препятствий Yuki достигает строки $n + 1$, поэтому вывод в примере верен.

Для второго примера:

• Серые клетки обозначают препятствия, а белые — пустые клетки. На следующем рисунке показаны все возможные расположения препятствий, удовлетворяющие требованиям:

• Легко доказать, что при любом из этих расположений препятствий, следуя ходам, указанным в выводе примера, Yuki достигнет строки $n + 1$.