Бұл есептің жеңіл нұсқасы. Жеңіл және күрделі нұсқалардың арасындағы жалғыз айырмашылық — шешіміңіздегі жүрістер санының шегінде.

Юки $n+1$ жолдан және $n$ бағаннан тұратын торда тұрады. Жолдар жоғарыдан төменге қарай $1$-ден $n+1$-ге дейін, ал бағандар солдан оңға қарай $1$-ден $n$-ге дейін нөмірленген. $i$-ші жол мен $j$-ші бағандағы ұяшықты $(i,j)$ арқылы белгілейік.

Торда $n-1$ кедергі бар және олардың орналасуы келесі шарттарды қанағаттандырады:

• $1$-ші жолда және $n+1$-ші жолда ешқандай кедергі жоқ.

• Барлық $2\le i\le n$ үшін $i$-ші жолда дәл бір кедергі бар.

• Барлық $1\le j\le n$ үшін $j$-ші бағанда ең көп дегенде бір кедергі бар.

Бастапқыда Юки $(1,1)$ ұяшығында тұр. Ол $n+1$-ші жолда кенгурулар тобы мекендейтінін естіп, сол жақтың табиғатын тамашалау үшін $n+1$-ші жолға барғысы келеді.

Мақсатына жету үшін Юки бірнеше жүріс жасай алады. Әр жүрісте ол төрт бағыттың бірін (жоғары, төмен, солға, оңға) таңдап, сол бағытта бір ұяшыққа жылжиды. Атап айтқанда, егер мақсатты ұяшық тордан тыс болса немесе онда кедергі болса, жүріс орындалмайды.

Өкінішке орай, Юки кедергілердің нақты орналасқан жерлерін емес, тек олардың орналасу ережелерін ғана біледі. Сондықтан ол кедергілердің кез келген жарамды орналасуы кезінде Юки қандай да бір сәтте $n+1$-ші жолға жететіндей жүрістер тізбегін көрсетуге көмектесуіңізді сұрайды (оған $n+1$-ші жолға кемінде бір рет жету жеткілікті; барлық жүрістер аяқталғаннан кейін сол жерде қалу міндетті емес).

Юки асықпағандықтан, сіздің шешіміңіздегі жүрістер саны $30\cdot n$-нен аспауы тиіс.

Кіріс деректер

Жалғыз жолда оң бүтін сан $n$ ($2\le n\le 10^3$) берілген.

Шығыс деректер

Бірінші жолда шешіміңіздегі жүрістер санын білдіретін бүтін сан $k$ ($1\le k\le30\cdot n$) шығарыңыз.

Екінші жолда ұзындығы $k$ болатын $s$ жолын шығарыңыз, мұндағы $s_i$ Юкидің $i$-ші жүрісінің бағытын білдіреді:

• Егер $s_i=\texttt{U}$ болса, Юки жоғары жылжиды.

• Егер $s_i=\texttt{D}$ болса, Юки төмен жылжиды.

• Егер $s_i=\texttt{L}$ болса, Юки солға жылжиды.

• Егер $s_i=\texttt{R}$ болса, Юки оңға жылжиды.

Мысалдар

Кіріс деректер мысалы 1

2

Шығыс деректер мысалы 1

4
DRDD

Кіріс деректер мысалы 2

3

Шығыс деректер мысалы 2

17
DDDUUURDDDUUURDDD

Ескертпе

Бірінші мысал үшін:

• Сұр ұяшықтар кедергілерді, ал ақ ұяшықтар бос ұяшықтарды білдірсін. Төмендегі суретте талаптарды қанағаттандыратын барлық мүмкін кедергілердің орналасулары көрсетілген:

• Кедергілердің бірінші орналасуы үшін Юкидің жолы: $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.

• Кедергілердің екінші орналасуы үшін Юкидің жолы: $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.

• Кедергілердің әрбір жарамды орналасуы үшін Юки $n+1$-ші жолға жетеді, сондықтан мысалдағы жауап дұрыс.

Екінші мысал үшін:

• Сұр ұяшықтар кедергілерді, ал ақ ұяшықтар бос ұяшықтарды білдірсін. Төмендегі суретте талаптарды қанағаттандыратын барлық мүмкін кедергілердің орналасулары көрсетілген:

• Осы кедергілер орналасуларының кез келгені үшін мысалдың шығысында берілген жүрістерді орындай отырып, Юки $n+1$-ші жолға жететінін дәлелдеу оңай.