Cells with value 1 are open and cells with value 0 are blocked. Move between open cells sharing a side. Find the minimum moves from (s,t) to (u,v). Coordinates are one-based.

Input

The first line contains n. The second line contains s, t, u, v. The next n lines contain the square grid.

• 2 <= n <= 1000

Output

Print the minimum moves, or -1 if the target is unreachable.

Example

Input

4
1 1 4 4
1 1 0 0
0 1 1 0
0 0 1 1
0 0 0 1

Output

6