هذه هي النسخة الصعبة من هذه المسألة. الفرق الوحيد بين النسختين السهلة والصعبة هو الحد الأقصى لعدد الحركات في حلك.

تعيش 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$ اتجاه حركة Yuki رقم $i$:

• إذا كان $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$ لأي من توزيعات العقبات هذه، باتباع الحركات المعطاة في إخراج المثال.