Questa è la versione facile di questo problema. L'unica differenza tra la versione facile e quella difficile è il limite sul numero di mosse nella tua soluzione.

Yuki vive su una griglia con $n+1$ righe e $n$ colonne. Le righe sono numerate da $1$ a $n+1$ dall'alto verso il basso, e le colonne sono numerate da $1$ a $n$ da sinistra a destra. Sia $(i,j)$ la cella alla riga $i$ e colonna $j$.

Ci sono $n-1$ ostacoli sulla griglia, e la loro distribuzione soddisfa le seguenti condizioni:

• Non ci sono ostacoli nella riga $1$ e nella riga $n+1$.

• Per ogni $2\le i\le n$, c'è esattamente un ostacolo nella riga $i$.

• Per ogni $1\le j\le n$, c'è al massimo un ostacolo nella colonna $j$.

Inizialmente, Yuki si trova in $(1,1)$. Ha sentito dire che un gruppo di canguri vive nella riga $n+1$, quindi vuole andare alla riga $n+1$ per vedere il panorama.

Per raggiungere il suo obiettivo, Yuki può effettuare diverse mosse. In ogni mossa, sceglie una delle quattro direzioni (su, giù, sinistra, destra) e si sposta di una cella in quella direzione. Nello specifico, se la cella di destinazione si trova fuori dalla griglia o contiene un ostacolo, la mossa non viene eseguita.

Sfortunatamente, Yuki conosce solo le regole per la distribuzione degli ostacoli, non le posizioni specifiche degli ostacoli. Pertanto, vuole che tu la aiuti a specificare la sequenza di mosse in modo tale che, per qualsiasi distribuzione valida degli ostacoli, Yuki raggiunga la riga $n+1$ a un certo punto (è sufficiente che abbia raggiunto la riga $n+1$ almeno una volta; non è necessario che rimanga lì dopo il completamento di tutte le mosse).

Poiché Yuki non ha fretta, il numero di mosse nella tua soluzione non deve superare $30\cdot n$.

Input

Una singola riga contiene un intero positivo $n$ ($2\le n\le 10^3$).

Output

Sulla prima riga stampa un intero $k$ ($1\le k\le30\cdot n$), che rappresenta il numero di mosse nella tua soluzione.

Sulla seconda riga stampa una stringa $s$ di lunghezza $k$, dove $s_i$ rappresenta la direzione dell'$i$-esima mossa di Yuki:

• Se $s_i=\texttt{U}$, Yuki si muove verso l'alto.

• Se $s_i=\texttt{D}$, Yuki si muove verso il basso.

• Se $s_i=\texttt{L}$, Yuki si muove verso sinistra.

• Se $s_i=\texttt{R}$, Yuki si muove verso destra.

Esempi

Input di esempio 1

2

Output di esempio 1

4
DRDD

Input di esempio 2

3

Output di esempio 2

17
DDDUUURDDDUUURDDD

Nota

Per il primo esempio:

• Siano le celle grigie gli ostacoli e le celle bianche le celle vuote. L'immagine seguente mostra tutte le possibili distribuzioni di ostacoli che soddisfano i requisiti:

• Per la prima distribuzione di ostacoli, il percorso di Yuki è $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.

• Per la seconda distribuzione di ostacoli, il percorso di Yuki è $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.

• Per ogni distribuzione valida di ostacoli, Yuki raggiunge la riga $n+1$, quindi l'output di esempio è corretto.

Per il secondo esempio:

• Siano le celle grigie gli ostacoli e le celle bianche le celle vuote. L'immagine seguente mostra tutte le possibili distribuzioni di ostacoli che soddisfano i requisiti:

• È facile dimostrare che per una qualsiasi di queste distribuzioni di ostacoli, seguendo le mosse indicate nell'output di esempio, Yuki raggiungerà la riga $n+1$.