Vang

Time limit1sMemory limit1024 MB

Summary

On a polygonal grid yard, a guard moving twice per turn chases a prisoner who can move or wait; report the guard turn when capture happens.

Level: Medium7 of 10
Topics: BFS, Graph, Game theory, Simulation
Solved: No attempts yet

Problem

A prison has a polygonal yard whose walls all run either north-south or east-west, and every wall segment is a whole number of metres long. The walls are given as a string, one metre at a time: N is one metre north, E east, S south, W west. The walls neither cross nor touch one another and together form a single closed polygon.

A prisoner has broken loose inside the yard and a guard is chasing him. A bomb shackled to the prisoner's leg keeps him from running fast, so the guard moves twice as fast as the prisoner. The prisoner and the guard take turns; the prisoner moves first.

Imagine the yard is divided into a grid of $1 \times 1$ metre cells. On his turn the prisoner moves to one orthogonally adjacent cell or stays in place. On his turn the guard makes two such moves. All movement is horizontal or vertical only, never diagonal.

Assuming the prisoner tries to evade the guard for as long as possible and the guard tries to catch him as quickly as possible, determine on which of the guard's own turns the guard catches the prisoner. The guard catches the prisoner the instant he reaches the prisoner's cell, which may happen on either of his two moves within a turn.

Input

The input has exactly four lines. Line 1 contains the total wall length $K$ ( $8 \le K \le 6000$ ). Line 2 contains a string of length $K$ made up of the characters N, E, S, W. Line 3 contains two space-separated integers: the $X$ and $Y$ coordinates of the prisoner. Line 4 contains two space-separated integers: the $X$ and $Y$ coordinates of the guard.

The cell immediately to the north-east (both north and east) of the wall string's starting point has coordinates $(0, 0)$ ; $X$ increases to the east and $Y$ increases to the north. The prisoner and the guard always start on different cells, and both starting cells are always inside the yard.

Output

Output a single integer: the number of the guard's turn on which he catches the prisoner.

Examples4

Example 1
Input
```
18
EESENEESSSWWWWWNNN
0 -1
2 -2
```
Expected output
```
2
```
Example 2
Input
```
18
EESENEESSSWWWWWNNN
4 -1
0 -3
```
Expected output
```
3
```
Example 3
Input
```
8
EESSWWNN
0 -1
1 -2
```
Expected output
```
1
```
Example 4
Input
```
14
EEEEEESWWWWWWN
0 -1
5 -1
```
Expected output
```
3
```