미로 탈출

당신은 눈을 가린 채 미로 안 어딘가에 놓였고, 지금 어느 칸에 서 있는지 전혀 알 수 없습니다. 하지만 미로의 구조는 알고 있습니다. 미로는 $n \times n$ 격자이며 각 칸은 벽(막힌 칸)이거나 빈 칸입니다. 당신은 이 지도를 모두 외우고 있고, 항상 어느 쪽이 북쪽인지 감지할 수 있습니다.

한 번의 이동으로 north(북), south(남), east(동), west(서) 중 한 방향으로 한 칸 움직일 수 있습니다. 이동하려는 칸이 벽이면 제자리에 그대로 머뭅니다. 격자의 바깥쪽 가장자리에 있는 칸에 도달하는 순간 탈출한 것으로 보며, 시작 칸이 이미 가장자리에 있다면 한 번도 움직이기 전에 이미 탈출한 상태입니다. 탈출한 뒤의 이동은 결과에 영향을 주지 않습니다.

시작 위치를 모르기 때문에, 어떤 빈 칸에서 출발하더라도 반드시 밖으로 나갈 수 있는 하나의 고정된 이동 순서를 미리 정해야 합니다. 모든 빈 칸에서 탈출이 가능하다고 가정해도 좋습니다.

첫째 줄에 양의 정수 $n$ ($1 \le n \le 8$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 $n$개의 문자가 주어져 미로의 한 행을 나타내며, 화면에서 위쪽이 북쪽입니다. 벽인 칸은 대문자 O로, 빈 칸은 마침표 .로 표시됩니다.

모든 가능한 빈 시작 칸에서 탈출을 보장하는 가장 짧은 이동 순서를 출력합니다. 한 줄에 하나씩, 각 줄은 정확히 north, south, east, west 중 하나입니다.

가장 짧은 이동 순서가 여러 개라면 사전순으로 가장 작은 것을 출력합니다. 두 순서를 한 이동씩 비교하여 처음으로 달라지는 위치에서, 이동을 나타내는 단어가 알파벳 순으로 더 앞선 쪽을 택합니다(east < north < south < west).

이동이 전혀 필요 없다면 — 모든 빈 칸이 이미 바깥쪽 가장자리에 있다면 — 아무것도 출력하지 않습니다.