Problem

KND is a student programmer at the University of Aizu. He is both a programmer and a fighter. He is known to be a sweet tooth, but he especially likes fresh cream. Eating fresh cream will allow you to break the concrete wall several times. Interested in its power, his neighbor decided to experiment with a new product, "Mato Cream," which was full of fresh cream.

In the experiment, first prepare a maze and lock KND in there. In the maze, there is a locked door, a key to open the door, and a mat cream in different squares. He can escape by picking up the fallen key and unlocking the door. It is possible to move to a square with a door without having a key. Also, eating matocream will allow you to break the maze wall N times. However, you cannot break the outer wall and get out of the maze. Now, how many squares can he move to escape the maze?

Sample The two mazes and the shortest escape route are shown in the following figure. S is KND's initial position, M is Mat Cream, K is the key, and D is the door.
<image>
<image>

Constraints

The input satisfies the following conditions.

• All inputs are integers.
• 2 ≤ W, H ≤ 20
• 0 ≤ xs, xm, xk, xd <W
• 0 ≤ ys, ym, yk, yd <H
• 0 ≤ N ≤ 100
• The coordinates of the initial position of the main character, the coordinates of the mat cream square, the coordinates of the key square, and the coordinates of the door square are different from each other.
• No dataset is impossible to enter the door.

Input

The input consists of multiple test cases. One test case is given in the following format. The end of the input is indicated by a line containing two zeros.

(Maze input)
xs ys ys
xm ym
xk yk
xd yd
N

here,

• Maze input:
  First comes the two integers W and H that represent the width and height of the maze. Then there is 2 * H-one line of input. The odd-numbered lines of these indicate the presence or absence of a wall between adjacent squares. There is one blank at the beginning, and W-one 1 or 0 comes. 1 means that there is a wall, 0 means that there is no wall. The even-numbered lines indicate the presence or absence of a wall between vertically adjacent squares. This comes with W 1s or 0s. Similarly, 1 means that there is a wall, and 0 means that there is no wall.
• xs ys: Coordinates of the square at the initial position of the main character
• xm ym: Coordinates of mato cream trout
• xk yk: Coordinates of the key cell
• xd yd: Coordinates of the door cell
• N: How many times you can break the maze wall when you take mato cream

Output

For each test case, output the minimum number of square movements that KND escapes from the maze in one line.

Examples

Input

3 3
0 0
0 0 0
0 0
0 0 1
0 1
0 0
0 1
1 1
2 2
1
5 5
0 1 0 0
1 0 0 1 0
1 0 1 0
0 1 0 0 1
0 1 1 0
0 1 0 1 0
1 1 1 0
0 0 0 0 0
0 0 1 1
0 0
1 0
4 4
0 1
2
0 0

Output

4
15

Input

3 3
0 0
0 0 0
0 0
0 0 1
0 1
0 0
0 1
1 1
2 2
1
5 5
0 1 0 0
1 0 0 1 0
1 0 1 0
0 1 0 0 1
0 1 1 0
0 1 0 1 0
1 1 1 0
0 0 0 0 0
0 0 1 1
0 0
1 0
4 4
0 1
2
0 0

Output

4
15

见题面

见题面