CF298B.Sail

The polar bears are going fishing. They plan to sail from $(s_{x},s_{y})$ to $(e_{x},e_{y})$ . However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at $(x,y)$ .

• If the wind blows to the east, the boat will move to $(x+1,y)$ .
• If the wind blows to the south, the boat will move to $(x,y-1)$ .
• If the wind blows to the west, the boat will move to $(x-1,y)$ .
• If the wind blows to the north, the boat will move to $(x,y+1)$ .

Alternatively, they can hold the boat by the anchor. In this case, the boat stays at $(x,y)$ . Given the wind direction for $t$ seconds, what is the earliest time they sail to $(e_{x},e_{y})$ ?

The first line contains five integers $t,s_{x},s_{y},e_{x},e_{y}$ $(1<=t<=10^{5},-10^{9}<=s_{x},s_{y},e_{x},e_{y}<=10^{9})$ . The starting location and the ending location will be different.

The second line contains $t$ characters, the $i$ -th character is the wind blowing direction at the $i$ -th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).

If they can reach $(e_{x},e_{y})$ within $t$ seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).

In the first sample, they can stay at seconds $1$ , $3$ , and move at seconds $2$ , $4$ .

In the second sample, they cannot sail to the destination.