Tämä on tehtävän helppo versio. Ainoa ero helpon ja vaikean version välillä on ratkaisusi siirtojen lukumäärän yläraja.

Yuki asuu ruudukolla, jossa on $n+1$ riviä ja $n$ saraketta. Rivit on numeroitu $1$:stä $n+1$:een ylhäältä alas, ja sarakkeet on numeroitu $1$:stä $n$:ään vasemmalta oikealle. Olkoon $(i,j)$ rivillä $i$ ja sarakkeessa $j$ oleva ruutu.

Ruudukolla on $n-1$ estettä, ja niiden sijoittelu täyttää seuraavat ehdot:

• Rivillä $1$ ja rivillä $n+1$ ei ole esteitä.

• Kaikilla $2\le i\le n$ rivillä $i$ on täsmälleen yksi este.

• Kaikilla $1\le j\le n$ sarakkeessa $j$ on enintään yksi este.

Aluksi Yuki on ruudussa $(1,1)$. Hän on kuullut, että rivillä $n+1$ asuu lauma kenguruita, joten hän haluaa mennä riville $n+1$ katsomaan maisemia.

Saavuttaakseen tavoitteensa Yuki voi tehdä useita siirtoja. Jokaisella siirrolla hän valitsee yhden neljästä suunnasta (ylös, alas, vasemmalle, oikealle) ja liikkuu yhden ruudun kyseiseen suuntaan. Tarkemmin sanottuna, jos kohderuutu on ruudukon ulkopuolella tai sisältää esteen, siirtoa ei suoriteta.

Valitettavasti Yuki tietää vain esteiden sijoittelua koskevat säännöt, ei esteiden tarkkoja sijainteja. Siksi hän haluaa sinun auttavan häntä määrittämään siirtojen jonon siten, että millä tahansa kelvollisella esteiden sijoittelulla Yuki saavuttaa rivin $n+1$ jossakin vaiheessa (riittää, että hän käy rivillä $n+1$ vähintään kerran; hänen ei tarvitse jäädä sinne kaikkien siirtojen päätyttyä).

Koska Yukilla ei ole kiire, ratkaisusi siirtojen lukumäärä saa olla enintään $30\cdot n$.

Syöte

Yksi rivi sisältää positiivisen kokonaisluvun $n$ ($2\le n\le 10^3$).

Tuloste

Tulosta ensimmäiselle riville kokonaisluku $k$ ($1\le k\le30\cdot n$), joka kuvaa ratkaisusi siirtojen lukumäärää.

Tulosta toiselle riville pituutta $k$ oleva merkkijono $s$, missä $s_i$ kuvaa Yukin $i$:nnen siirron suuntaa:

• Jos $s_i=\texttt{U}$, Yuki liikkuu ylös.

• Jos $s_i=\texttt{D}$, Yuki liikkuu alas.

• Jos $s_i=\texttt{L}$, Yuki liikkuu vasemmalle.

• Jos $s_i=\texttt{R}$, Yuki liikkuu oikealle.

Esimerkit

Esimerkkisyöte 1

2

Esimerkkituloste 1

4
DRDD

Esimerkkisyöte 2

3

Esimerkkituloste 2

17
DDDUUURDDDUUURDDD

Huomautus

Ensimmäisessä esimerkissä:

• Olkoot harmaat ruudut esteitä ja valkoiset ruudut tyhjiä ruutuja. Seuraava kuva näyttää kaikki mahdolliset vaatimukset täyttävät esteiden sijoittelut:

• Ensimmäisellä esteiden sijoittelulla Yukin reitti on $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.

• Toisella esteiden sijoittelulla Yukin reitti on $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.

• Jokaisella kelvollisella esteiden sijoittelulla Yuki saavuttaa rivin $n+1$, joten esimerkkituloste on oikein.

Toisessa esimerkissä:

• Olkoot harmaat ruudut esteitä ja valkoiset ruudut tyhjiä ruutuja. Seuraava kuva näyttää kaikki mahdolliset vaatimukset täyttävät esteiden sijoittelut:

• On helppo todistaa, että millä tahansa näistä esteiden sijoitteluista Yuki saavuttaa rivin $n+1$ seuraamalla esimerkkitulosteessa annettuja siirtoja.