B. Sail

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Input

The first line contains five integers t, s_x, s_y, e_x, e_y (1 ≤ t ≤ 10⁵,  - 10⁹ ≤ s_x, s_y, e_x, e_y ≤ 10⁹). 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).

Sample test(s)

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.

 第一次用C#交题~

1 using System; 2  3 class Slove 4 { 5     public static int Main() 6     { 7         int t, sx, sy, ex, ey, ans = 0; 8         string mov; 9         string str = Console.ReadLine();10         string[] sstr = str.Split(' ');11         t = Convert.ToInt32(sstr[0]);12         sx = Convert.ToInt32(sstr[1]);13         sy = Convert.ToInt32(sstr[2]);14         ex = Convert.ToInt32(sstr[3]);15         ey = Convert.ToInt32(sstr[4]);16         //Console.WriteLine(t + " " + sx + " " + sy + " " + ex + " " + ey);17         mov = Console.ReadLine();18         foreach (char c in mov)19         {20             if (sx == ex && sy == ey) break;21             ans++;22             switch (c)23             {24                 case 'E':25                     if (ex > sx) sx++;26                     break;27                 case 'S':28                     if (ey < sy) sy--;29                     break;30                 case 'W':31                     if (ex < sx) sx--;32                     break;33                 case 'N':34                     if (ey > sy) sy++;35                     break;36             }37         }38         if (sx == ex && sy == ey) Console.WriteLine(ans);39         else Console.WriteLine(-1);40         return 0;41     }42 }