To jest łatwa wersja tego zadania. Jedyną różnicą między wersją łatwą a trudną jest ograniczenie liczby ruchów w twoim rozwiązaniu.

Yuki mieszka na siatce o $n+1$ wierszach i $n$ kolumnach. Wiersze są ponumerowane od $1$ do $n+1$ od góry do dołu, a kolumny od $1$ do $n$ od lewej do prawej. Niech $(i,j)$ oznacza pole w wierszu $i$ i kolumnie $j$.

Na siatce jest $n-1$ przeszkód, których rozmieszczenie spełnia następujące warunki:

• W wierszach $1$ i $n+1$ nie ma przeszkód.

• Dla każdego $2\le i\le n$ w wierszu $i$ jest dokładnie jedna przeszkoda.

• Dla każdego $1\le j\le n$ w kolumnie $j$ jest co najwyżej jedna przeszkoda.

Początkowo Yuki znajduje się na polu $(1,1)$. Słyszała, że w wierszu $n+1$ mieszka grupa kangurów, więc chce dotrzeć do wiersza $n+1$, aby podziwiać krajobraz.

Aby osiągnąć cel, Yuki może wykonać kilka ruchów. W każdym ruchu wybiera jeden z czterech kierunków (w górę, w dół, w lewo, w prawo) i przesuwa się o jedno pole w tym kierunku. Jeśli jednak pole docelowe jest poza siatką lub zawiera przeszkodę, ruch nie zostaje wykonany.

Niestety Yuki zna jedynie zasady rozmieszczenia przeszkód, a nie ich konkretne położenie. Dlatego chce, abyś pomógł jej ustalić ciąg ruchów taki, że dla każdego poprawnego rozmieszczenia przeszkód Yuki w pewnym momencie dotrze do wiersza $n+1$ (wystarczy, że dotrze do wiersza $n+1$ przynajmniej raz; nie musi tam pozostać po wykonaniu wszystkich ruchów).

Ponieważ Yuki się nie spieszy, liczba ruchów w twoim rozwiązaniu nie może przekraczać $30\cdot n$.

Wejście

Jedyny wiersz zawiera dodatnią liczbę całkowitą $n$ ($2\le n\le 10^3$).

Wyjście

W pierwszym wierszu wypisz liczbę całkowitą $k$ ($1\le k\le30\cdot n$), oznaczającą liczbę ruchów w twoim rozwiązaniu.

W drugim wierszu wypisz napis $s$ długości $k$, w którym $s_i$ oznacza kierunek $i$-tego ruchu Yuki:

• Jeśli $s_i=\texttt{U}$, Yuki przesuwa się w górę.

• Jeśli $s_i=\texttt{D}$, Yuki przesuwa się w dół.

• Jeśli $s_i=\texttt{L}$, Yuki przesuwa się w lewo.

• Jeśli $s_i=\texttt{R}$, Yuki przesuwa się w prawo.

Przykład

Wejście 1

2

Wyjście 1

4
DRDD

Wejście 2

3

Wyjście 2

17
DDDUUURDDDUUURDDD

Uwagi

Dla pierwszego przykładu:

• Niech szare pola oznaczają przeszkody, a białe pola — puste miejsca. Poniższy rysunek przedstawia wszystkie możliwe rozmieszczenia przeszkód spełniające wymagania:

• Dla pierwszego rozmieszczenia przeszkód trasa Yuki to $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.

• Dla drugiego rozmieszczenia przeszkód trasa Yuki to $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.

• Dla każdego poprawnego rozmieszczenia przeszkód Yuki dociera do wiersza $n+1$, więc przykładowe wyjście jest poprawne.

Dla drugiego przykładu:

• Niech szare pola oznaczają przeszkody, a białe pola — puste miejsca. Poniższy rysunek przedstawia wszystkie możliwe rozmieszczenia przeszkód spełniające wymagania:

• Łatwo udowodnić, że dla każdego z tych rozmieszczeń przeszkód Yuki dotrze do wiersza $n+1$, wykonując ruchy podane w przykładowym wyjściu.