A fly is flying on a gridding. Stupid enough, it always flies in the direction "up, left, down, right, up, left, down, right, up, ...". In every step, the fly can choose to move in the specified direction, or to stay still. Each grid has its property, indicated by an integer:
A "-1" indicates that the grid is a barrier where the fly can not enter.
A "0" indicates the grid has nothing in.
A positive integer n indicates a trap in the grid which will hold the fly for the following n seconds. Although the fly can turn its direction, it can't move a bit.
Given the fly's starting position, you shall tell at least how many steps the fly needs to arrive the given target position.
Input
There are multiple testcases.
Each testcase begins with a line with the grids' width W and height H (1 <= W, H <= 20), the starting position (in row and column), the ending position (in row and column). You may assume that the starting position is always valid, that is, it will not be a "-1" grid.
Then H lines follows, each have W integers, indicating the grids.
Output
For each testcase, output one line containing the minimum steps. If it's impossible for the fly to arrive the target position, output -1 instead.
Sample Input
2 2 1 0 0 1
0 0
0 0
2 2 1 0 0 1
-1 0
0 -1
Sample Output
4
-1
