In dieser interaktiven Aufgabe musst du vom Eingang eines unbekannten Labyrinths zu dessen Ausgang gelangen, ohne zu viel Zeit zu benötigen.

Der berühmte Krieger Malcolm, der Held von Arcania, wanderte nachts durch einen dunklen Wald. Er war schon lange unterwegs und begann zu glauben, er habe sich verirrt, als er plötzlich auf eine Steinmauer auf seinem Weg stieß. Die Zeichen auf der Steinplatte, die unter herabgefallenen Blättern zu sehen waren, zeigten eindeutig, dass er ein Labyrinth zwergischen Ursprungs entdeckt hatte.

Der Held weiß wenig über den Wald und die dort wachsenden Bäume. Dafür hat er viel Zeit in Gesellschaft von Zwergen verbracht und kann nun allein anhand der Zeichen viel über ein Labyrinth erfahren.

Die Zeichen auf diesem Labyrinth bilden die Zeichenfolge „SK3“. Das Zeichen „S“ bedeutet, dass das Labyrinth quadratisch ist: Sein Boden besteht aus $n \times n$ quadratischen Zellen von jeweils $1 \times 1$ Metern. Um diese Zellen verläuft eine dünne, durchgehende Mauer mit zwei Öffnungen. Die erste ist der Eingang, neben dem der Held steht. Er befindet sich in der Südwand der südwestlichen Eckzelle des Labyrinths. Die zweite Öffnung ist der Ausgang in der Nordwand der nordöstlichen Eckzelle.

Zwei Zellen mit einer gemeinsamen Seite können durch einen Durchgang verbunden oder durch einen ein Meter langen Abschnitt einer dünnen Innenwand getrennt sein. Von jeder Zelle kann man in jede seitlich benachbarte Zelle gehen, wenn keine Wand dazwischenliegt. Außerdem kann man den Ausgang frei passieren. Der Eingang ist nur so lange offen, bis der Held das Labyrinth betritt. Danach schließt er sich sofort und öffnet sich erst wieder, wenn der Held sicher am Ausgang angekommen ist.

Die Zeichen „K3“ verraten einem erfahrenen Labyrinthwanderer, dass das Labyrinth die folgende Struktur besitzt. Zuerst wird aus allen möglichen Abschnitten dünner Innenwände (insgesamt gibt es $n \times (n-1)$ Abschnitte in Nord-Süd-Richtung und genauso viele in Ost-West-Richtung) zufällig ein Drittel ausgewählt, wobei eine nicht ganzzahlige Anzahl abgerundet wird. Diese Abschnitte werden in einer festgelegten zufälligen Reihenfolge betrachtet und anschließend in dieser Reihenfolge in das Labyrinth eingesetzt. Würde das Einsetzen eines Abschnitts das Quadrat des Labyrinths in nicht verbundene Teile zerlegen, wird dieser Abschnitt verworfen und nicht eingesetzt. Somit ist garantiert, dass das entstehende Labyrinth zusammenhängend ist.

Malcolm freute sich: Er weiß so viel über das Labyrinth, dass er den Ausgang gewiss erreichen kann. Sein Ziel ist es, auf der Waldzelle neben dem Eingang zu starten und die Waldzelle neben dem Ausgang zu erreichen. Außerdem sollte er sich beeilen: Wer schnell genug vom Eingang zum Ausgang gelangt, wird den im Wald nahe dem Ausgang verborgenen Schatz sehen. Natürlich gilt dies nur, wenn niemand den Schatz schon zuvor erreicht hat.

Bei näherem Nachdenken gibt es jedoch Grund zur Sorge. Erstens kennt Malcolm die Größe des Labyrinths nicht: Die Seitenlänge des Quadrats $n$ kann jede ganze Meterzahl von $10$ bis $200$ sein. Zweitens ist das Labyrinth genauso dunkel wie der umliegende Wald, sodass Malcolm sich beinahe blind bewegen muss. Zu Beginn jedes Schritts wählt der Held eine der vier Hauptrichtungen: Norden, Osten, Süden oder Westen. Dann versucht er, sich einen Meter in diese Richtung zu bewegen. Stößt er auf ein Hindernis, bleibt er an seinem bisherigen Ort. Andernfalls bewegt er sich in die benachbarte Zelle in der gewählten Richtung. Die Dauer jedes Schritts hängt nicht von dessen Ergebnis ab, daher zählt die Gesamtzahl der Schritte.

Hilf dem Helden, sich so zu bewegen, dass er die gewünschte Zelle schnell genug erreicht. Die Lösung gilt als korrekt, wenn der Held höchstens $5 \cdot n + 300$ Schritte macht und die Zelle außerhalb des Labyrinthausgangs erreicht.

Interaktion

In dieser Aufgabe reagiert das Juryprogramm auf Befehle, die eine Lösung auf die Standardausgabe schreibt. Jeder Befehl bestimmt Malcolms nächsten Schritt. Ein Befehl steht in einer eigenen Zeile und besteht aus einem englischen Großbuchstaben: „N“ für einen Schritt nach Norden, „E“ nach Osten, „S“ nach Süden und „W“ nach Westen.

Auf jeden ausgegebenen Befehl antwortet das Juryprogramm sofort mit einer Zeile auf der Standardeingabe der Lösung. Diese enthält ein Wort aus englischen Kleinbuchstaben: „no“, wenn ein Hindernis den Durchgang verhindert hat, „ok“, wenn der Schritt erfolgreich war, der Held aber die Zielzelle noch nicht erreicht hat, und „end“, wenn der Schritt erfolgreich war und der Held die Zielzelle erreicht hat. Nach der Antwort „end“ muss sich die Lösung ohne weitere Ausgabe beenden.

Um eine Pufferung der Ausgabe zu verhindern, leere nach jedem Befehl den Ausgabepuffer. Das geht beispielsweise mit fflush (stdout) in C oder C++, System.out.flush () in Java, flush (output) in Pascal oder sys.stdout.flush () in Python.

In jedem Test wird das Labyrinth nach seiner zufälligen Erzeugung im Voraus festgelegt.

Hat eine Lösung mindestens $100\,000$ Schritte gemacht, aber weder das Zeitlimit überschritten noch die Zielzelle erreicht, wird der Test mit dem Ergebnis „Falsche Antwort“ beendet.

Beispiele

Hinweis

Das obige Bild zeigt das im ersten Test erzeugte Labyrinth. Malcolm beginnt in der mit einem Kreis markierten Zelle und muss die mit einem Kreuz markierte Zelle erreichen. Dieses Labyrinth lässt sich beispielsweise mit der folgenden Befehlsfolge durchqueren (unter den Befehlen stehen die Ergebnisse ihrer Ausführung):

N W N E N W N E N E E E S E E N N N N N E N E S E E N
ok no ok ok ok ok ok ok ok ok ok no ok ok ok ok ok ok ok ok ok ok ok no ok ok end

Im Bild ist diese Lösung durch eine dicke graue Linie dargestellt.