本题没有可用的提交语言。

题目描述

你被蒙上眼睛后置于一个迷宫中的某处，你不清楚自己的位置。不过你知道这个迷宫是基于网格布局的，且每个网格位置要么是被阻挡的，要么是可通行的。实际上，你已经记住了迷宫的地图，而且凭借你独特的感知能力，你总能辨别出北方的方向。

在这个迷宫里，你有四种可行的移动方式：向北、向南、向东和向西。你的任务是找出最短的移动序列，无论你在迷宫中的初始位置如何，这个序列都能确保你成功逃脱。当你到达网格的外边缘方格时，就意味着你已经“逃脱”了（如果你一开始就在外边缘方格，那么你已经逃脱了）。一旦逃脱，后续的移动就无关紧要了。如果你试图朝着墙壁移动，你将停留在原地。

你可以假定从迷宫中每个可通行的位置都能够逃脱。

输入

输入包含一个正整数 $n$（$n \leq 8$），接着是 $n$ 行，每行表示一个 $n \times n$ 网格的一行。这个网格描述了你被困的迷宫。在屏幕显示中，上方为北方。被阻挡的位置用字符 “O”（大写字母 “o”）表示，可通行的位置用字符 “.” 表示。

输出

输出由若干行组成，每行包含 “north”、“south”、“east” 或 “west” 中的一个，代表能确保从任何可能的可通行起始位置逃脱的最短移动序列。

如果存在多个可能的最短序列，输出其中任意一个即可。

输入数据 1

4
OO.O
...O
OO..
O..O

输出数据 1

east
north

题目来源

Waterloo local 1999.06.19