Þetta er auðvelda útgáfan af þessu verkefni. Eini munurinn á auðveldu og erfiðu útgáfunni er hámarkið á fjölda leikja í lausninni þinni.
Yuki býr á grind með $n+1$ röðum og $n$ dálkum. Raðirnar eru númeraðar frá $1$ til $n+1$ að ofan og niður, og dálkarnir eru númeraðir frá $1$ til $n$ frá vinstri til hægri. Látum $(i,j)$ tákna reitinn í röð $i$ og dálki $j$.
Það eru $n-1$ hindranir á grindinni og dreifing þeirra uppfyllir eftirfarandi skilyrði:
Það eru engar hindranir í röð $1$ og röð $n+1$.
Fyrir öll $2\le i\le n$ er nákvæmlega ein hindrun í röð $i$.
Fyrir öll $1\le j\le n$ er í mesta lagi ein hindrun í dálki $j$.
Í upphafi er Yuki á $(1,1)$. Hún hefur heyrt að hópur kengúra búi í röð $n+1$, svo hún vill fara í röð $n+1$ til að skoða útsýnið.
Til að ná markmiði sínu getur Yuki framkvæmt nokkra leiki. Í hverjum leik velur hún eina af áttunum fjórum (upp, niður, vinstri, hægri) og færir sig um einn reit í þá átt. Nánar tiltekið, ef markreiturinn er utan grindarinnar eða inniheldur hindrun, þá er leikurinn ekki framkvæmdur.
Því miður þekkir Yuki aðeins reglurnar um dreifingu hindrananna, en ekki nákvæma staðsetningu þeirra. Þess vegna vill hún að þú hjálpir sér að tilgreina runu leikja þannig að fyrir sérhverja gilda dreifingu hindrana komist Yuki í röð $n+1$ á einhverjum tímapunkti (hún þarf aðeins að hafa komist í röð $n+1$ að minnsta kosti einu sinni; hún þarf ekki að vera þar ennþá eftir að öllum leikjum er lokið).
Þar sem Yuki liggur ekki á, má fjöldi leikja í lausninni þinni ekki fara yfir $30\cdot n$.
Inntak
Ein lína inniheldur jákvæða heiltölu $n$ ($2\le n\le 10^3$).
Úttak
Í fyrstu línunni skal prenta heiltölu $k$ ($1\le k\le30\cdot n$), sem táknar fjölda leikja í lausninni þinni.
Í annarri línunni skal prenta streng $s$ af lengd $k$, þar sem $s_i$ táknar stefnu $i$-ta leiks Yuki:
Ef $s_i=\texttt{U}$ færir Yuki sig upp.
Ef $s_i=\texttt{D}$ færir Yuki sig niður.
Ef $s_i=\texttt{L}$ færir Yuki sig til vinstri.
Ef $s_i=\texttt{R}$ færir Yuki sig til hægri.
Dæmi
Dæmi um inntak 1
2
Dæmi um úttak 1
4 DRDD
Dæmi um inntak 2
3
Dæmi um úttak 2
17 DDDUUURDDDUUURDDD
Athugasemd
Fyrir fyrra dæmið:
- Látum gráa reiti tákna hindranir og hvíta reiti tákna tóma reiti. Eftirfarandi mynd sýnir allar mögulegar dreifingar hindrana sem uppfylla kröfurnar:
Fyrir fyrri dreifingu hindrana er leið Yuki $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.
Fyrir seinni dreifingu hindrana er leið Yuki $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.
Fyrir sérhverja gilda dreifingu hindrana kemst Yuki í röð $n+1$, svo úttakið í dæminu er rétt.
Fyrir seinna dæmið:
- Látum gráa reiti tákna hindranir og hvíta reiti tákna tóma reiti. Eftirfarandi mynd sýnir allar mögulegar dreifingar hindrana sem uppfylla kröfurnar:
- Auðvelt er að sanna að fyrir hvaða sem er af þessum dreifingum hindrana mun Yuki komast í röð $n+1$ með því að fylgja leikjunum sem gefnir eru í úttaki dæmisins.