A knight may land only on cells with value 1. Find its minimum number of 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 board.

• 2 <= n <= 1000

Output

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

Example

Input

5
1 1 5 5
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

Output

4