Untitled

There is a forest fire and you are in the forest.

If an area (x,y) burns at time t, the adjacent area (x+1,y),(x-1,y),(x,y+1),(x,y-1) will burn at time t+1 .

Unfortunately, when you are notified, the forest fire has been lasting for minutes after the first burning area was reported.

If you are in (x,y) at time t , you can only move to (x+/-1,y+/-1) at time t+1.

The only exit of the forest is in (ex,ey), and there are some obstacles in the forest.

Note that the exit and obstacles(*) are NOT burnable.

Can you calculate the minimal time required for you to escape from the forest?

At time 1, the first burning area is in (fx,fy) .
At time k, you are in (sx,sy) .
Input Format

The first line is H,W which is height and width of the map for the forest.

The following H line is the map, and there are W characters in each line.

Following the lines for map, there are remaining 3 lines:

The first line is (fx,fy), which is the coordinates of the first burning area.
The second line is k, which is the elapsed time after the first burning area was reported.
The third line is (sx,sy) and (ex,ey) , which are the coordinates of you when you are notified and the coordinates of the exit.
Constraints

The range of coordinates is (0,0) to (H-1,W-1)
The top left coordinates of the map is(0,0) .
The down right coordinates of the map is (H-1,W-1).
All coordinates in input are distinct.
Output Format

If you can safely escape from the forest, print the minimal time required; otherwise, print Help! instead.

Sample Input 0

10 18
*****************
*...*.......**..*
**..*....*.*.*..*
*......*.**.**.**
*..**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************
1 1
4
4 1 3 3
Sample Output 0

6