在这个交互式问题中，你需要在不花费太多时间的情况下，从一个未知迷宫的入口到达出口。

著名的战士、阿卡尼亚的英雄马尔科姆（Malcolm）夜间穿过一片黑暗的森林。他走了很久，开始觉得自己迷路了，但突然在路上撞到了一堵石墙。在落叶下隐约可见的石板上的标记清楚地表明，他发现了一个矮人建造的迷宫。

英雄对这片森林和生长在那里的树木知之甚少。但好在，他曾与矮人们共度了很长时间，所以现在他只需看看迷宫的标记，就能对迷宫了解很多。

这个迷宫上的标记组成了字符“SK3”。字符“S”表示迷宫是一个正方形，也就是说，迷宫的地面由 $n \times n$ 个大小为 $1 \times 1$ 米的正方形网格组成。这些网格周围有一堵薄薄的实心外墙，外墙上有两个开口。第一个是入口，英雄就站在它旁边。它位于迷宫西南角网格的南侧墙壁上。第二个开口是出口，位于迷宫东北角网格的北侧墙壁上。

迷宫中任意两个相邻（共享一条边）的网格，既可以通过通道相连，也可以被一段长为一米的薄内墙隔开。在迷宫中，如果两个相邻网格之间没有墙，就可以从一个网格移动到另一个网格。此外，可以自由通过出口移动。入口仅在英雄步入迷宫之前是敞开的。在此之后，它会立即关闭，并且只有在英雄安全到达出口时才会再次打开。

字符“K3”告诉经验丰富的迷宫探索者，该迷宫具有以下结构。首先，在所有可能的薄内墙段中（总共有 $n \times (n-1)$ 段南北向的内墙，以及同样数量的东西向内墙），随机选择三分之一（非整数则向下取整），并以随机的固定顺序进行考虑。然后，按照该顺序将这些墙段放置到迷宫中。如果放置某个墙段会导致包含迷宫的正方形区域被分割成不连通的部分，则丢弃（不放置）该墙段。因此，保证最终生成的迷宫是连通的。

马尔科姆高兴起来：他对这个迷宫了解如此之多，以至于他肯定能到达出口。他的目标是从与迷宫入口相邻的森林网格开始，到达与迷宫出口相邻的森林网格。此外，他必须抓紧时间：足够快地从入口走到出口的人将会看到隐藏在出口附近森林中的宝藏。当然，上述说法只有在没有其他人先拿到宝藏的情况下才成立。

仔细想想，也有一些令人担心的事情。首先，马尔科姆不知道迷宫的大小：正方形边长 $n$ 可以是 $10$ 到 $200$ 之间的任意整数。其次，迷宫和周围的森林一样黑暗，所以马尔科姆几乎必须盲目移动。在每一步开始时，英雄选择四个主要方向之一：北（North）、东（East）、南（South）或西（West）。然后他尝试朝该方向移动一米。如果英雄撞到障碍物，他会留在原地。否则，他会移动到所选方向的相邻网格。每一步所需的时间不取决于该步的结果，因此重要的是总步数。

帮助英雄移动，使他能足够快地到达目标网格。如果英雄最多使用 $5 \cdot n + 300$ 步并到达迷宫出口外的网格，则该解法将被视为正确。

交互格式

在这个问题中，评测程序会根据你的程序输出到标准输出的命令做出反应。每个命令决定了马尔科姆的下一步。每个命令写在单独的一行中，由一个大写英文信件组成：“N”表示向北走，“E”表示向东走，“S”表示向南走，“W”表示向西走。

对于每个发出的命令，评测程序会立即向程序的标准输入发送一行响应，其中包含一个英文小写单词：“no”表示有障碍物阻挡了通道，“ok”表示移动成功但英雄尚未到达目标网格，“end”表示移动成功且英雄已到达目标网格。在收到“end”作为响应后，程序必须终止，不得再进行任何输出。

为了防止输出缓冲，请在发出每个命令后刷新输出缓冲区：例如，在 C 或 C++ 中使用 fflush(stdout)，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)，或在 Python 中使用 sys.stdout.flush()。

在每个测试点中，迷宫在随机生成后是预先固定的。

如果程序进行了至少 $100\,000$ 步，但尚未超过时间限制且未到达目标网格，测试将以“Wrong Answer”结果终止。

样例

输入样例 1

ok
no
ok
ok
ok
ok
ok
ok
ok
ok
ok
no
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
no
ok
ok
end

输出样例 1

N
W
N
E
N
W
N
E
N
E
E
E
S
E
E
N
N
N
N
N
E
N
E
S
E
E
N

说明

上图显示了在第一个测试点中生成的迷宫。马尔科姆从标有圆圈的网格开始，必须到达标有叉号的网格。例如，可以使用以下命令序列通过该迷宫（命令下方是其执行结果）：

在图中，该解法由一条粗灰色线表示。