Problem Statement

We have an $N \times N$ chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.

• If S_{i,j}= ., the square (i, j) is empty.
• If S_{i,j}= #, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.

Input

Input is given from Standard Input in the following format:
N
A_x A_y
B_x B_y
S_1
S_2
$\vdots$
S_N

Output

Print the answer.

Constraints

• $2 \le N \le 1500$
• $1 \le A_x,A_y \le N$
• $1 \le B_x,B_y \le N$
• $(A_x,A_y) \neq (B_x,B_y)$
• S_i is a string of length N consisting of . and #.
• S_{A_x,A_y}= .
• S_{B_x,B_y}= .

Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...

....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

• $(1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)$

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).

Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9

见题面 Input 部分

见题面 Output 部分