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

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 ממהרת, מספר המהלכים בפתרון שלכם אינו יכול לעלות על $10 \cdot n$.

קלט

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

פלט

בשורה הראשונה הדפיסו מספר שלם $k$ ($1 \le k \le 10 \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$.