Це складна версія цієї задачі. Єдина відмінність між простою та складною версіями — обмеження на кількість ходів у вашому розв’язку.

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$.