Bessie steckt wieder auf der falschen Seite von Farmer Johns Scheune fest. Wegen ihrer schlechten Sicht braucht sie Hilfe beim Durchqueren.

Die Scheune ist ein $N \times N$-Gitter quadratischer Zellen ($2 \leq N \leq 20$), leer oder mit unpassierbaren Heuballen. Sie geht von unten links $(1,1)$ nach oben rechts $N,N$. Befehle sind „vorwärts“, „90 Grad links drehen“, „90 Grad rechts drehen“. Gesucht ist die kürzeste Folge. Bei einem Schritt aus dem Gitter, in die Wand, oder in Heu bleibt sie stehen und überspringt den Befehl.

Sie weiß nicht, ob sie anfangs nach oben zu $(1,2)$ oder rechts zu $(2,1)$ blickt. Die kürzeste Folge muss beide Fälle lösen. Nach Ankunft ignoriert sie weitere Befehle.

Eingabe

Lies von der Standardeingabe.

Die erste Zeile enthält $N$.

Die nächsten $N$ Zeilen haben genau $N$ Zeichen. Das erste der letzten ist $(1,1)$, das letzte der ersten ist $(N,N)$.

H bezeichnet Heu, E eine leere Zelle.

$(1,1)$ und $N,N$ sind leer, und ein Weg leerer Zellen von $(1,1)$ nach $N, N$ ist garantiert.

Ausgabe

Schreibe auf die Standardausgabe.

Gib eine Zeile mit der kürzesten Befehlsfolgenlänge für beide Anfangsrichtungen nach oben oder rechts aus.

Beispiele

Eingabe 1

3
EHE
EEE
EEE

Ausgabe 1

9

Hinweis

„Vorwärts, rechts, vorwärts, vorwärts, links, vorwärts, links, vorwärts, vorwärts“ funktioniert im Beispiel für beide Richtungen.

Autor der Aufgabe: Brian Dean