Escape from the Dark City

The dark city is represented by an $n \times m$ grid of 0-1 characters. For every cell $a_{i,j}$, a value of $1$ indicates an obstacle that cannot be passed, and a value of $0$ indicates a free cell.

Small A and Sal share the same initial position $(x_1,y_1)$, while the Fear Demon King starts from position $(x_2,y_2)$. The goal of small A is to reach the Fear Demon King's position.

Sal (and likewise the Fear Demon King) will move according to a route specified by a string consisting of the digits $0$ to $4$. At the $i$th second, let $r = R[((i-1) \mod L)]$ where $L$ is the length of the route string. The movement rules are as follows:

• If $r = 0$, then Sal remains in place.
• If $r = 1$, Sal attempts to move one cell up.
• If $r = 2$, Sal attempts to move one cell down.
• If $r = 3$, Sal attempts to move one cell left.
• If $r = 4$, Sal attempts to move one cell right.

If the destination cell is an obstacle or outside the maze, Sal (and the Fear Demon King) remain in place.

Every second, small A may choose to move one cell in one of the four cardinal directions or stay still; however, he can only move to a cell that is free (i.e. not a wall) and within the maze.

There is a twist: due to the eerie properties of the dark city, small A can only remain continuously outside the "aura" of Sal for at most $s$ seconds. The aura’s effective radius is $d$, meaning that if the Euclidean distance between small A at $(x,y)$ and Sal at $(xx,yy)$ satisfies $$\sqrt{(x-xx)^2+(y-yy)^2} \le d,$$ then small A is within the aura. Once small A re-enters the aura after having been outside, his "time outside" counter resets to zero. If small A remains outside Sal's aura for more than $s$ seconds continuously, he dies.

Both Sal and the Fear Demon King start moving from second 1 following the above movement rule (using the digit sequence repeatedly). At time 0, their positions are the given initial positions.

Your task is to determine the minimum number of seconds small A needs to reach the Fear Demon King's position, or output -1 if it is impossible.

inputFormat

The input consists of:

1. One line with two integers n and m ($1 \le n,m \le 100$) indicating the number of rows and columns of the maze.
2. n lines each containing a string of length m made up of characters '0' and '1'.
3. One line with two integers x1 and y1 (the starting position for small A and Sal).
4. One line with two integers x2 and y2 (the starting position for the Fear Demon King).
5. One line with an integer s and a number d (the maximum allowed seconds to be outside Sal's aura and the aura radius, respectively).
6. One line containing the route string R consisting of digits from 0 to 4. Its length is $L\ge1$.

Positions are 1-indexed. It is guaranteed that the starting positions are in free cells (i.e. the grid cell contains '0').

outputFormat

Output a single integer representing the minimum number of seconds small A needs to reach the Fear Demon King's position. If it is impossible, output -1.

sample

3 3
000
010
000
1 1
3 3
2 1
144

4

</p>