Shortcut

Time limit1sMemory limit128 MB

Summary

Given a self-avoiding grid walk of unit segments, find the shortest horizontal or vertical connector between two visited break points that is not already part of the path, with tie-breaking rules.

Level: Hard8 of 10
Topics: Geometry, Hash map, Sorting, Simulation
Solved: No attempts yet

Statement

Mirek has a favourite route that he walks from home to the university every working day. The route is made up of sections, and each section is a straight segment 10 meters long. Each section either continues straight ahead from the previous section or is perpendicular to it. After walking each section, Mirek takes a short break to admire the beauty of nature. During his walk he never visits the same place twice.

Yesterday Mirek stayed up late at a party, and today he got up late. He knows that unless he changes his usual route he will miss the first lecture. He plans to take exactly one shortcut, and he wants it to be as short as possible (between us, he does not really want to be on time — he just wants to ease his conscience). The shortcut must be a horizontal or vertical segment connecting two break points of Mirek's route.

Help Mirek find the shortest shortcut.

Write a program that:

reads Mirek's route,
computes the shortest shortcut on the route,
writes the result.

Input

The first line contains one integer n (3 ≤ n ≤ 250 000), the number of sections of the route. The second line contains a sequence of n characters N, E, S, or W with no spaces in between. Each character describes one section of the route: N, E, S, or W means that Mirek walks 10 meters north, east, south, or west respectively. You may assume that at least one shortcut exists for the given route.

Output

Output a single line containing the integers l, b, e and the character d, separated by single spaces. Integer l is the length of the shortest shortcut (measured in 10 m segments). Integers b and e are the numbers of the break points where the shortcut begins and ends respectively (break points are numbered with consecutive integers from 0 for Mirek's home to n for the university). Character d is the direction of the shortcut. If more than one shortcut of minimal length exists, output the one that begins earliest on the route. If more than one shortcut of minimal length begins at the same break point, output the one that ends furthest along the route.

Examples5

Example 1
Input
```
12
NNNENNWWWSSW
```
Expected output
```
2 3 11 W
```
Example 2
Input
```
6
NNEESS
```
Expected output
```
2 0 6 E
```
Example 3
Input
```
3
NES
```
Expected output
```
1 0 3 E
```
Example 4
Input
```
6
EENNWW
```
Expected output
```
2 0 6 N
```
Example 5
Input
```
6
EESSWW
```
Expected output
```
2 0 6 S
```