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

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 не спешит, число ходов в вашем решении не должно превышать $30\cdot n$.

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

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

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

В первой строке выведите целое число $k$ ($1\le k\le30\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$.