You are a plastic bag located at ~(0,0)~ on an infinite 2D grid.

For the next ~m~ units of time, you know the weather forecast. At each time ~i~ (~1 \leq i \leq m~), the wind blows in one of the following directions: north, east, south, west, or no wind.

Initially, you are stationary. At any time, you may choose to stop being stationary. Once you do, you will drift following the wind for all future times.

If you are at position ~(x,y)~ at time ~i-1~ and the wind at time ~i~ is:

• N, you will move to ~(x, y+1)~
• S, you will move to ~(x, y-1)~
• E, you will move to ~(x+1, y)~
• W, you will move to ~(x-1, y)~
• X, you will remain at ~(x, y)~

There are also ~n~ Good Citizens. Each Good Citizen occupies a fixed grid cell. If you ever enter a cell occupied by a Good Citizen, they will put you in the bin, and you are immediately removed from the grid.

You are given a target cell ~(x_t,y_t)~. Determine the earliest time ~s~ ~(0 \leq s \leq m)~ at which you can stop being stationary such that:

• the bag reaches ~(x_t,y_t)~ at some time ~s \leq t \leq m~, and
• the bag never enters a cell occupied by a Good Citizen before reaching ~(x_t,y_t)~.

If no such starting time exists, output -1.

Input

The first line contains two space-separated integers ~m~ and ~n~ ~(1 \leq m \leq 10^5, 0 \leq n \leq 100)~, representing the number of turns of wind that will follow and the number of Good Citizens.

The next line also contains two space-separated integers ~x_t~ and ~y_t~ ~(-10^9 \leq x_t,y_t \leq 10^9)~, the coordinates of the target cell.

The following line contains a single string of ~m~ characters, where each character is one of N, S, E, W, X. The ~i~th character represents the weather at the ~i~th time from ~1~ to ~m~.

The following ~n~ lines each contain integers ~x_i~ and ~y_i~ ~(-10^9 \leq x_i, y_i\leq 10^9)~, the position of one of the ~n~ Good Citizens. Note that ~n~ may be zero.

Output

Output a single integer - the earliest time ~s~ at which you can stop being stationary such that the bag reaches ~(x_t,y_t)~ at some time ~t \geq s~, and the bag never enters a cell occupied by a Good Citizen before reaching ~(x_t,y_t)~.

If no such starting time exists, output -1.

Notes

If the bag stops being stationary at time ~s~, it remains at ~(0,0)~ for the first ~s~ wind steps, and then begins moving according to the wind at time ~s+1~.

The bag is removed if it occupies a cell containing a Good Citizen at any time from when it starts drifting until it reaches the target, including the starting cell and the target cell itself.

Example

Input 1

3 1
1 0
NES
1 1

Output 1

1

If you start at ~s=0~, you go to ~(0,1)~ then ~(1,1)~ and are removed by the Good Citizen there. If you wait until ~s=1~, you move to ~(1,0)~ and reach the target safely.

Input 2

2 0
1 0
NN

Output 2

-1

No matter when you stop being stationary, the wind only moves north, so the ~x~-coordinate stays ~0~. You can never reach the target ~(1,0)~.

Input 3

7 1
2 0
NESWEEX
0 1

Output 3

4