지름길

미렉(Mirek)은 집에서 대학교까지 매 평일 걸어 다니는, 가장 좋아하는 경로가 있습니다. 이 경로는 여러 구간(section)으로 이루어져 있고, 각 구간은 길이가 10미터인 직선 선분입니다. 각 구간은 바로 앞 구간을 곧게 이어 나가거나, 바로 앞 구간과 수직을 이룹니다. 미렉은 한 구간을 지날 때마다 잠시 멈춰 자연의 아름다움을 감상합니다. 걷는 동안 그는 같은 지점을 두 번 지나지 않습니다.

어제 미렉은 파티에서 밤늦게까지 깨어 있었고, 오늘은 늦잠을 잤습니다. 평소 경로를 바꾸지 않으면 첫 강의를 놓치게 된다는 것을 그는 알고 있습니다. 그래서 그는 지름길을 딱 하나만 만들려고 하는데, 그 지름길이 되도록 짧기를 바랍니다(사실 그는 제시간에 도착하고 싶은 것이 아니라 그저 양심의 가책을 덜고 싶을 뿐이라는 것을 살짝 알려드립니다). 지름길은 반드시 미렉의 경로에 있는 두 정지점(break point)을 잇는 수평 또는 수직 선분이어야 합니다.

미렉이 가장 짧은 지름길을 찾도록 도와주세요.

다음을 수행하는 프로그램을 작성하세요.

• 미렉의 경로를 읽어 들이고,
• 경로에서 가장 짧은 지름길을 계산하고,
• 그 결과를 출력합니다.

첫 번째 줄에는 경로의 구간 수를 나타내는 정수 n (3 ≤ n ≤ 250 000)이 주어집니다. 두 번째 줄에는 공백 없이 이어진 n개의 문자 N, E, S, W가 주어집니다. 각 문자는 경로의 한 구간을 나타냅니다. 문자 N, E, S, W는 각각 미렉이 북쪽, 동쪽, 남쪽, 서쪽으로 10미터 걷는다는 뜻입니다. 주어진 경로에는 적어도 하나의 지름길이 존재한다고 가정해도 좋습니다.

출력은 한 줄로 이루어지며, 정수 l, b, e와 문자 d를 하나의 공백으로 구분하여 담습니다. 정수 l은 가장 짧은 지름길의 길이입니다(10미터 선분의 개수로 측정). 정수 b와 e는 각각 지름길이 시작하고 끝나는 정지점의 번호입니다(정지점은 미렉의 집을 0으로 하여 대학교인 n까지 차례로 번호를 매깁니다). 문자 d는 지름길의 방향입니다. 최소 길이의 지름길이 여러 개라면, 경로에서 가장 먼저 시작하는 것을 출력합니다. 최소 길이이면서 같은 정지점에서 시작하는 지름길이 여러 개라면, 경로에서 가장 멀리(늦게) 끝나는 것을 출력합니다.