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

Yuki mieszka na planszy mającej $n + 1$ wierszy i $n$ kolumn. 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 planszy znajduje się $n - 1$ przeszkód, a ich 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$ znajduje się dokładnie jedna przeszkoda.

• Dla każdego $1 \le j \le n$ w kolumnie $j$ znajduje się 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 udać się do wiersza $n + 1$, aby podziwiać widoki.

Aby osiągnąć swój cel, Yuki może wykonać pewną liczbę ruchów. W każdym ruchu wybiera jeden z czterech kierunków (góra, dół, lewo, prawo) i przesuwa się o jedno pole w tym kierunku. Jeśli jednak pole docelowe leży poza planszą lub zawiera przeszkodę, ruch nie jest wykonywany.

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

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

Wejście

Jeden 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 \le 10 \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 porusza się w górę.

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

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

• Jeśli $s_i = \texttt{R}$, Yuki porusza 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 oznaczają puste pola. 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)$.

• Przy każdym poprawnym rozmieszczeniu 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 oznaczają puste pola. 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.