Dies ist die schwere Version dieser Aufgabe. Der einzige Unterschied zwischen der einfachen und der schweren Version ist die Obergrenze für die Anzahl der Bewegungen in deiner Lösung.

Yuki lebt auf einem Gitter mit $n + 1$ Zeilen und $n$ Spalten. Die Zeilen sind von oben nach unten mit $1$ bis $n + 1$ nummeriert, die Spalten von links nach rechts mit $1$ bis $n$. Mit $(i, j)$ bezeichnen wir das Feld in Zeile $i$ und Spalte $j$.

Auf dem Gitter befinden sich $n - 1$ Hindernisse, deren Verteilung die folgenden Bedingungen erfüllt:

• In Zeile $1$ und Zeile $n + 1$ gibt es keine Hindernisse.

• Für alle $2 \le i \le n$ gibt es in Zeile $i$ genau ein Hindernis.

• Für alle $1 \le j \le n$ gibt es in Spalte $j$ höchstens ein Hindernis.

Anfangs befindet sich Yuki auf $(1, 1)$. Sie hat gehört, dass eine Gruppe Kängurus in Zeile $n + 1$ lebt, und möchte deshalb nach Zeile $n + 1$ gehen, um die Landschaft zu betrachten.

Um ihr Ziel zu erreichen, kann Yuki mehrere Bewegungen ausführen. Bei jeder Bewegung wählt sie eine der vier Richtungen (oben, unten, links, rechts) und bewegt sich ein Feld in diese Richtung. Liegt das Zielfeld außerhalb des Gitters oder enthält es ein Hindernis, wird die Bewegung jedoch nicht ausgeführt.

Leider kennt Yuki nur die Regeln für die Verteilung der Hindernisse, nicht deren genaue Positionen. Daher möchte sie, dass du ihr hilfst, eine Bewegungsfolge festzulegen, mit der Yuki bei jeder gültigen Hindernisverteilung irgendwann Zeile $n + 1$ erreicht (sie muss Zeile $n + 1$ nur mindestens einmal erreicht haben; nach Abschluss aller Bewegungen muss sie nicht dort bleiben).

Da Yuki es eilig hat, darf die Anzahl der Bewegungen in deiner Lösung $10 \cdot n$ nicht überschreiten.

Eingabe

Eine einzelne Zeile enthält eine positive ganze Zahl $n$ ($2 \le n \le 10^3$).

Ausgabe

Gib in der ersten Zeile eine ganze Zahl $k$ ($1 \le k \le 10 \cdot n$) aus, die die Anzahl der Bewegungen in deiner Lösung angibt.

Gib in der zweiten Zeile eine Zeichenkette $s$ der Länge $k$ aus, wobei $s_i$ die Richtung von Yukis $i$-ter Bewegung angibt:

• Falls $s_i = \texttt{U}$, bewegt sich Yuki nach oben.

• Falls $s_i = \texttt{D}$, bewegt sich Yuki nach unten.

• Falls $s_i = \texttt{L}$, bewegt sich Yuki nach links.

• Falls $s_i = \texttt{R}$, bewegt sich Yuki nach rechts.

Beispiele

Eingabe 1

2

Ausgabe 1

4
DRDD

Eingabe 2

3

Ausgabe 2

17
DDDUUURDDDUUURDDD

Hinweis

Zum ersten Beispiel:

• Graue Felder stellen Hindernisse dar, weiße Felder leere Felder. Die folgende Abbildung zeigt alle möglichen Hindernisverteilungen, die die Anforderungen erfüllen:

• Bei der ersten Hindernisverteilung ist Yukis Weg $(1, 1) \to (1, 1) \to (1, 2) \to (2, 2) \to (3, 2)$.

• Bei der zweiten Hindernisverteilung ist Yukis Weg $(1, 1) \to (2, 1) \to (2, 1) \to (3, 1) \to (3, 1)$.

• Bei jeder gültigen Hindernisverteilung erreicht Yuki Zeile $n + 1$, daher ist die Beispielausgabe korrekt.

Zum zweiten Beispiel:

• Graue Felder stellen Hindernisse dar, weiße Felder leere Felder. Die folgende Abbildung zeigt alle möglichen Hindernisverteilungen, die die Anforderungen erfüllen:

• Es lässt sich leicht beweisen, dass Yuki bei jeder dieser Hindernisverteilungen Zeile $n + 1$ erreicht, wenn sie den in der Beispielausgabe angegebenen Bewegungen folgt.