Description

不久前，在一个遥远的热带国度，住着三只橡皮鸭。炎炎夏日，当它们在沙滩上休憩时，决定乘着一把黑色的旧雨伞，顺着洋流去附近的一个小岛冒险。

由于这几只鸭子都是经验丰富的海洋探险家，出发前它们会先查看一张洋流地图。地图上，鸭子们所在的岛屿用字母 'o' 标记。它们可以选择朝四个方向之一出发：北（N）、东（E）、西（W）、南（S）。

海域中的洋流总是朝某一个方向流动，在地图上用如下符号表示：西向东用 '<'，东向西用 '>'，北向南用 'v'，南向北用 '^'。当鸭子们处于有洋流的格子上时，会被洋流带到下一个格子，方向与洋流一致。这片海域的洋流有个特点：不会把鸭子带出地图边界，也不会形成漩涡（即不会让鸭子陷入循环）。

风平浪静的海面用 '.' 表示。如果鸭子们被洋流带到平静的海面，或者回到了起始岛屿，它们就无法继续航行。鸭子们要去的目标小岛用字母 'x' 标记。

鸭子们可不想耽误沙滩派对，于是请求你帮忙判断：它们是否有可能到达目标小岛？如果可以，应该从哪个方向出发？由于其中一只鸭子容易晕船，请你选择能让航程最短的方向。如果有多个方向航程相同，请选择字典序最小的那个方向。

Input Format

第一行输入两个整数 $r$ 和 $s$（$3 \leq r, s \leq 100$），表示地图的行数和列数。

接下来 $r$ 行，每行 $s$ 个字符，字符集为 'o<>v^.x'，表示洋流地图。地图上恰好有一个 'o' 和一个 'x'。'o' 不会出现在第一行、最后一行、第一列或最后一列。

Output Format

如果鸭子们无法到达目标小岛，输出一行 :(。

否则，第一行输出 :)，第二行输出出发方向（N、E、W、S）。

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

:)
E

5 5
v<<<<
>v.>^
v<.o.
>>v>v
..>>x

:)
S

3 3
x>.
.o^
^<.

:(

Hint

对前两个样例的说明：

• 第一个样例中，只有朝东（E）出发才能到达目标岛屿，其他方向都会停在风平浪静的海面上。
• 第二个样例中，朝北或朝南出发都能到达目标岛屿，但南（S）方向更短，应选择南。

评分

在价值 $30$ 分的测试点中，若存在合法出发方向，则唯一。

翻译由 ChatGPT-4.1 完成。