Walking on a Chessboard

Time Limit: 1 Second    Memory Limit: 32768 KB

A mini robot is put on a cell of a chessboard. The size of the chessboard is 8 * 8. The robot has four states denoted by integer from 1 to 4.

There is an integer in each cell of the chessboard, the integers are positive and not greater than 1000. The robot can walk up, down, left or right to one of the neighboring cells. The cost of the movement is the multiplication of the integer in the new cell and its original state, then the state of the robot is altered to (cost MOD 4 + 1). The initial state of the robot is 1.

Your task is to find the path between two given cells with the minimum total cost. Total cost is the sum of the costs for each walk along the path.

Input

The input contains multiple test cases. Each test case begins with a line containing the row number and column number of the start cell and the target cell. Row number and column number will be within 1 and 8. 8 lines follow, each with 8 integers. This is the chessboard configuration.

There will be a blank line between subsequent test cases. The last line of the input will have 4 zeros which signals the end of the input and should not be processed.

Output

For each test case, print the minimum total cost on a line.

Sample Input

1 1 2 2
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

0 0 0 0

Sample Output

3

Submit

Source: Zhejiang University Local Contest 2004