Problem2084--鸭子度假

2084: 鸭子度假

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

鸭子度假 查看测评数据信息

不久前,在遥远的热带土地上,住着三只橡皮鸭。一个炎热的夏日,他们

躺在沙滩上,鸭子决定前往附近的一个岛屿。由于鸭子喜欢冒险,

他们决定撑着一把旧的黑伞,乘着洋流去旅行。

由于鸭子是经验丰富的海洋探险家,所以在航行前他们会查看海洋地图

洋流。在地图上,鸭子居住的岛屿用字母“o”标记。鸭子可以开始了

他们在四个方向中的任何一个方向航行:北 – N、东 – E、西 – W 和南 – S。

这些海域的洋流向四个方向之一移动,并在地图上标记为以下

方式:东西向'<'、东西向'>'、南北向'v'和南北向'^'。当鸭子位于

一个有洋流的单元格,它们会沿着洋流的方向移动一个单元格。这些海域的洋流

很特别,因为它们从不带出地图,也不会形成漩涡(鸭子所在的地方)。

平静的海面用一个点“.”标记。如果水流将鸭子带到海面平静的海面或返回

出发岛,他们将无法继续航行。鸭子们想去的岛是用字母“x”标记。

鸭子不想停止他们的海滩派对。他们恳请您告诉他们是否有可能

去另一个岛屿,如果是,他们应该向哪个方向开始他们的航程。由于其中之一

鸭子会晕船,他们会要求您选择可以使航程尽可能短的方向。

如果有多个方向产生相同的最短旅行时间,您应该选择

一个按字母顺序排列的第一个。



输入格式

第一行包含整数 r 和 s(3 ≤ r,s ≤ 100),即地图的行数和列数。

接下来的 r 行中的每一行都包含来自集合 'o<>v^.x' 的字符,它们表示海洋地图

洋流。 地图上总是只有一个字符“o”和一个字符“x”。

 字符 'o' 永远不会位于第一行或最后一行,也不会在第一列或者最后一列。



输出格式

如果鸭子无法到达另一个岛,则在第一行输出  :(

否则,在第一行输出 :)  且在第二行输出起始方向(N 或 E 或W或 S )。 

Input




Output



Sample Input Copy

6 6
..>>>v
.o^..v
.v.<.v
.>>^.v
.x<<<<
......

Sample Output Copy

:)
E

HINT

【样例输入2】
3 3
x>.
.o^
^<.
【样例输出2】
:(
【样例输入3】
5 5
v<<<<
>v.>^
v<.o.
>>v>v
..>>x
【样例输出3】
:)
S

Source/Category