問題文

ここに、 $N \\times N$ のチェス盤があります。このチェス盤の上から $i$ 行目、左から $j$ 列目にあるマスをマス $(i,j)$ と呼びます。
チェス盤の情報は $N$ 個の文字列 $S_i$ として与えられます。
文字列 $S_i$ の $j$ 文字目である $S_{i,j}$ には、以下の情報が含まれています。

• $S_{i,j}=$ . のとき マス $(i,j)$ には何も置かれていない。
• $S_{i,j}=$ # のとき マス $(i,j)$ には白のポーンが $1$ つ置かれている。このポーンを動かしたり取り除いたりすることはできない。

この盤面のマス $(A_x,A_y)$ に、白のビショップを $1$ つ置きました。
この白のビショップをチェスのルール (注記参照) に従ってマス $(A_x,A_y)$ からマス $(B_x,B_y)$ に移動させるために必要な最小の手数を求めてください。
ただし、移動できない場合は代わりに -1 を出力してください。

注記

マス $(i,j)$ に置かれている白の ビショップ は、 $1$ 手で以下のルールに従って移動することができます。

• 各正整数 $d$ について、以下の条件を全て満たせばマス $(i+d,j+d)$ に移動できる。

  • マス $(i+d,j+d)$ が盤内に存在する
  • 全ての正整数 $l \\le d$ について、 $(i+l,j+l)$ に白のポーンがない

• 各正整数 $d$ について、以下の条件を全て満たせばマス $(i+d,j-d)$ に移動できる。

  • マス $(i+d,j-d)$ が盤内に存在する
  • 全ての正整数 $l \\le d$ について、 $(i+l,j-l)$ に白のポーンがない

• 各正整数 $d$ について、以下の条件を全て満たせばマス $(i-d,j+d)$ に移動できる。

  • マス $(i-d,j+d)$ が盤内に存在する
  • 全ての正整数 $l \\le d$ について、 $(i-l,j+l)$ に白のポーンがない

• 各正整数 $d$ について、以下の条件を全て満たせばマス $(i-d,j-d)$ に移動できる。

  • マス $(i-d,j-d)$ が盤内に存在する
  • 全ての正整数 $l \\le d$ について、 $(i-l,j-l)$ に白のポーンがない

制約

• $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$ は . および # からなる $N$ 文字の文字列
• $S_{A_x,A_y}=$ .
• $S_{B_x,B_y}=$ .

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_x$ $A_y$ $B_x$ $B_y$ $S_1$ $S_2$ $\\vdots$ $S_N$

出力

答えを出力せよ。

入力例 1

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

出力例 1

3

以下のように移動させることで $3$ 手でビショップを $(1,3)$ から $(3,5)$ まで移動させることができます。 $2$ 手以内でビショップを $(1,3)$ から $(3,5)$ まで移動させることはできません。

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

入力例 2

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

出力例 2

-1

どのようにビショップを動かしても $(3,2)$ から $(4,2)$ に移動させることはできません。

入力例 3

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

出力例 3

9