問題文

迷路を解くのが好きな K 理事長は，迷路になりそうなマス目を見つけた．マス目は縦 R 行，横 C 列の長方形の形をしており，各マスは白または黒で塗られている．上から i 行目 (1 \leqq i \leqq R)，左から j 列目 (1 \leqq j \leqq C) のマスをマス (i, j) と呼ぶことにする．

K 理事長は，マス目の白いマスは通れるマス，黒いマスは通れないマスとして，迷路を解くことにした．具体的には，以下のようにして迷路を解く．

1. 白いマスの中からスタートのマス (S_r, S_c) とゴールのマス (G_r, G_c) を選ぶ．
2. 上下左右に隣接する白いマスに移動することを繰り返して，スタートのマスからゴールのマスへ移動する経路を見つける．

K 理事長はスタートのマスとゴールのマスを決めたが，マス目の色の塗られ方によっては，白いマスのみを通ってスタートからゴールへ移動する経路が存在しない場合があることに気がついた．そこで， K 理事長の持っている N \times N マスの大きさのハンコを用いて以下の操作を繰り返すことで，スタートからゴールへ移動する経路が存在するようにしたい．

操作：マス目から N \times N マスの正方形の領域を選び，この領域に含まれるマスをすべて白にする．より厳密には，1 \leqq a \leqq R - N + 1，1 \leqq b \leqq C - N + 1 を満たす整数 a, b を選び，a \leqq i \leqq a + N - 1，b \leqq j \leqq b + N - 1 を満たすすべての整数の組 (i, j) に対して，マス (i, j) を白にする．

ハンコを使うと手が汚れる可能性があるため，操作回数はできるだけ少なくしたい．マス目の塗られ方とハンコの大きさ，スタートのマスとゴールのマスが与えられたとき，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようにするための，操作回数の最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq R \leqq C．
• R \times C \leqq 6\,000\,000．
• 1 \leqq S_r \leqq R．
• 1 \leqq S_c \leqq C．
• 1 \leqq G_r \leqq R．
• 1 \leqq G_c \leqq C．
• (S_r, S_c) \neq (G_r, G_c)．
• A_i (1 \leqq i \leqq R) は . または # からなる長さ C の文字列である．
• マス (S_r, S_c) の色は白である．
• マス (G_r, G_c) の色は白である．
• R, C, N, S_r, S_c, G_r, G_c は整数である．

小課題

1. (8 点) N = 1，R \times C \leqq 1\,500\,000．
2. (19 点) R \times C \leqq 1\,000．
3. (16 点) 答えは 10 以下である，R \times C \leqq 1\,500\,000．
4. (19 点) R \times C \leqq 60\,000．
5. (5 点) R \times C \leqq 150\,000．
6. (19 点) R \times C \leqq 1\,500\,000．
7. (8 点) R \times C \leqq 3\,000\,000．
8. (6 点) 追加の制約はない．

入力例 1

2 4 2
1 1
2 4
.###
###.

出力例 1

1

(a, b) = (1, 2) を選んで 1 回操作を行い，マス (1, 2), (1, 3), (2, 2), (2, 3) を白にすると，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようになる．例えば，経路 (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4) はその 1 つである．

操作を 1 回も行わない場合，白いマスのみを通ってスタートからゴールへ移動する経路は存在しないから，1 を出力する．

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす．

入力例 2

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

出力例 2

4

この入力例はすべての小課題の制約を満たす．

入力例 3

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

出力例 3

1

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす．

入力例 4

1 15 1
1 15
1 1
...............

出力例 4

0

操作を 1 回も行わなくても，白いマスのみを通ってスタートからゴールへ移動する経路が存在する場合がある．

この入力例はすべての小課題の制約を満たす．