Dies ist die einfache Version dieser Aufgabe. Der einzige Unterschied zwischen der einfachen und der schweren Version ist die Begrenzung der 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 von $1$ bis $n+1$ nummeriert, die Spalten von links nach rechts von $1$ bis $n$. Mit $(i,j)$ wird die Zelle in Zeile $i$ und Spalte $j$ bezeichnet.

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

• In Zeile $1$ und Zeile $n+1$ befinden sich keine Hindernisse.

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

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

Zu Beginn befindet sich Yuki bei $(1,1)$. Sie hat gehört, dass in Zeile $n+1$ eine Gruppe Kängurus 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 um eine Zelle in diese Richtung. Wenn die Zielzelle außerhalb des Gitters liegt oder ein Hindernis enthält, wird die Bewegung allerdings nicht ausgeführt.

Leider kennt Yuki nur die Regeln für die Verteilung der Hindernisse, aber nicht deren genaue Positionen. Deshalb möchte sie, dass du ihr hilfst, eine Bewegungsfolge anzugeben, sodass Yuki bei jeder zulässigen 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 nicht eilig hat, darf die Anzahl der Bewegungen in deiner Lösung $30\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\le30\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 Zellen stellen Hindernisse und weiße Zellen leere Zellen dar. 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 zulässigen Hindernisverteilung erreicht Yuki Zeile $n+1$, daher ist die Beispielausgabe korrekt.

Zum zweiten Beispiel:

• Graue Zellen stellen Hindernisse und weiße Zellen leere Zellen dar. 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.