זוהי הגרסה הקלה של בעיה זו. ההבדל היחיד בין הגרסה הקלה לגרסה הקשה הוא המגבלה על מספר המהלכים בפתרון שלכם.

Yuki גרה על רשת בעלת $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$ יש לכל היותר מכשול אחד.

בתחילה Yuki נמצאת ב־$(1,1)$. היא שמעה שקבוצת קנגורו גרה בשורה $n+1$, ולכן היא רוצה להגיע לשורה $n+1$ כדי לצפות בנוף.

כדי להשיג את מטרתה, Yuki יכולה לבצע כמה מהלכים. בכל מהלך היא בוחרת אחד מארבעת הכיוונים (למעלה, למטה, שמאלה, ימינה) וזזה תא אחד בכיוון זה. בפרט, אם תא היעד נמצא מחוץ לרשת או מכיל מכשול, המהלך אינו מתבצע.

לרוע המזל, Yuki מכירה רק את הכללים לסידור המכשולים, ולא את המיקומים המדויקים שלהם. לכן היא רוצה שתעזרו לה לקבוע רצף מהלכים כך שבכל סידור חוקי של מכשולים, Yuki תגיע בשלב כלשהו לשורה $n+1$ (עליה להגיע לשורה $n+1$ לפחות פעם אחת בלבד; היא אינה חייבת להישאר שם לאחר סיום כל המהלכים).

מכיוון ש־Yuki אינה ממהרת, מספר המהלכים בפתרון שלכם לא יכול לעלות על $30\cdot n$.

קלט

שורה יחידה מכילה מספר שלם חיובי $n$ ($2\le n\le 10^3$).

פלט

בשורה הראשונה הדפיסו מספר שלם $k$ ($1\le k\le30\cdot n$), המייצג את מספר המהלכים בפתרון שלכם.

בשורה השנייה הדפיסו מחרוזת $s$ באורך $k$, כאשר $s_i$ מייצג את הכיוון של המהלך ה־$i$ של Yuki:

• אם $s_i=\texttt{U}$, Yuki זזה למעלה.

• אם $s_i=\texttt{D}$, Yuki זזה למטה.

• אם $s_i=\texttt{L}$, Yuki זזה שמאלה.

• אם $s_i=\texttt{R}$, Yuki זזה ימינה.

דוגמאות

קלט 1

2

פלט 1

4
DRDD

קלט 2

3

פלט 2

17
DDDUUURDDDUUURDDD

הערה

עבור הדוגמה הראשונה:

• תאים אפורים מייצגים מכשולים ותאים לבנים מייצגים תאים ריקים. התמונה הבאה מציגה את כל סידורי המכשולים האפשריים המקיימים את הדרישות:

• עבור סידור המכשולים הראשון, המסלול של Yuki הוא $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.

• עבור סידור המכשולים השני, המסלול של Yuki הוא $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.

• בכל סידור חוקי של מכשולים, Yuki מגיעה לשורה $n+1$, ולכן הפלט לדוגמה נכון.

עבור הדוגמה השנייה:

• תאים אפורים מייצגים מכשולים ותאים לבנים מייצגים תאים ריקים. התמונה הבאה מציגה את כל סידורי המכשולים האפשריים המקיימים את הדרישות:

• קל להוכיח שעבור כל אחד מסידורי המכשולים הללו, ביצוע המהלכים הנתונים בפלט לדוגמה יביא את Yuki לשורה $n+1$.