You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

桃花岛其实也没什么好玩的，黄蓉经常偷偷跑到江湖上与洪七公等人玩。于是，黄药师就经常想一些游戏与女儿玩，为了是把黄蓉留在身边，江湖险恶啊！

这次黄药师又想了一种模拟游戏，游戏是这样的：她把整个桃花岛划分成一个坐标系。游戏开始前，黄蓉站在平面坐标系的一个点上，而她的闺房在坐标系的另一个点上，任何时候，她可以从当前所在点跨一步达到她周围的上、下、左、右四个点，黄药师不断地说四个字“东（E）”、“南（S）”、“西（W）”、“北（N）”，则黄蓉就想象着不断地从一个点走到另一个点，直至到自己的闺房为止。

比如，黄蓉开始时站在 $\rm A$ 点，她的家在 $\rm B$ 点，黄药师连续说了一串：$\verb!NNNENNWWWSSW!$，则走了如下一个线路。然后，黄药师会问黄蓉：中间有没有走“弯路”了？即有没有捷径好走？比如，下图中就有多条捷径，可以从 $\rm C$ 走 $\verb!NN!$ 而到 $\rm E$，或走 $\verb!WW!$ 直接到 $\rm D$。

注意：捷径必须是直线。

黄药师听说你是一个程序设计高手，就想请你编个程序帮他测测这个游戏的难度，以便改进游戏规则后再让黄蓉挑战。

你的任务是：找一条最短的捷径。

输入格式

第一行是一个整数 $n$（$3\le n\le 2.5\times 10^5$）表示黄药师所报出的字符串长度。

第二行是一个由 $\verb!N!,\verb!E!,\verb!S!,\verb!W!$ 组成的字符串，都是大写字母且中间没有空格。

我们把游戏的起点记为 $0$，把黄蓉的闺房（即游戏的终点）记为 $n$，中间的每一个落脚点都依次标记一个自然数。

输出格式

输出只有一行，由 $3$ 个数字和 $1$ 个字符组成，中间用1个空格隔开。

• 第 $1$ 个数字表示最短捷径的长度。
• 第 $2$ 个数字表示最短捷径的开始点。
• 第 $3$ 个数字表示最短捷径的结束点。
• 最后一个字符表示最短捷径的方向（同样用 $\verb!N!,\verb!E!,\verb!S!,\verb!W!$ 中的一个表示）。

如果最短捷径存在多个解，那么输出开始点标号最小的那一条。如果仍然有多个解，那么输出结束点标号最大的。数据保证一定存在满足条件的最短捷径。

12
NNNENNWWWSSW

2 3 11 W