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

题目描述

Mirek每天从家到大学有一条固定路线，这条路线由若干段组成，每段都是10米长的直线段。每段要么是前一段的直线延伸，要么与前一段垂直。走完每段后，Mirek会稍作休息，欣赏自然美景。在行走过程中，他从不重复经过同一地点。

昨晚Mirek熬夜参加派对，今天起床晚了。他知道如果不改变往常的路线，就会错过第一堂课。他计划只做一次捷径，但希望这个捷径尽可能短（其实他只是想安抚自己的良心）。捷径必须是连接路线中两个休息点的水平或垂直线段。

请帮助Mirek找到最短的捷径。

任务

编写一个程序：

1. 读取Mirek的路线。
2. 计算路线上的最短捷径。
3. 输出结果。

输入格式

输入的第一行包含一个整数n（3 ≤ n ≤ 250000），表示路线的段数。第二行包含一个由n个字符N、E、S或W组成的序列，字符间无空格。每个字符表示路线的其中一段：N表示向北走10米，E表示向东走10米，S表示向南走10米，W表示向西走10米。可以保证给定路线上至少存在一条捷径。

输出格式

输出的第一行也是唯一一行包含四个部分：整数l、b、e和字符d，用单个空格分隔。整数l表示最短捷径的长度（以10米为单位）。整数b和e分别表示捷径起点和终点的休息点编号（休息点从0开始编号，0表示家，n表示大学）。字符d表示捷径的方向。如果存在多条最短捷径，输出起点最早的那条；如果起点相同，输出终点最远的那条。

输入样例1

12
NNNENNWWWSSW

输出样例1

2 3 11 W

来源

Central Europe 2003