The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 180 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

greedy

implementation

*1200

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Sail

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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})?

Input

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).

Output

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

Examples

Input

5 0 0 1 1

SESNW

Output

4

Input

10 5 3 3 6

NENSWESNEE

Output

-1

Note

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 15:09:05 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|