Maze Escape

You wake up blindfolded, dropped somewhere inside a maze, with no idea which cell you are standing on. You do know the maze itself: it is an $n \times n$ grid where every cell is either blocked (a wall) or free, and you have memorized this map. You can also always tell which way is north.

At each step you may move north, south, east, or west. A move takes you one cell in that direction; if the destination cell is a wall, you stay exactly where you are. You have escaped the instant you stand on a cell on an outer edge of the grid — if your starting cell is already on an edge, you have escaped before making any move, and moves made after escaping do not matter.

Since you do not know where you started, you must commit in advance to a single fixed sequence of moves that is guaranteed to lead you out no matter which free cell you began on. You may assume that every free cell is able to escape.

The first line contains a positive integer $n$ ($1 \le n \le 8$). Each of the following $n$ lines contains $n$ characters describing one row of the maze, with north pointing up on the screen. A blocked cell is written as the uppercase letter O, and a free cell as a dot ..

Output the shortest sequence of moves that guarantees escape from every possible free starting cell, printing one move per line — each line being exactly north, south, east, or west.

If more than one shortest sequence exists, output the lexicographically smallest one: compare two sequences move by move and, at the first position where they differ, prefer the sequence whose move word comes earlier in alphabetical order (east < north < south < west).

If no move is needed — every free cell already lies on an outer edge — output nothing.