迷路 (Maze)

문제

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

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

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

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

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

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

입력

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

R C N
S_r S_c
G_r G_c
A_1
A_2
...
A_R

$A_i$ ($1 \le i \le R$) は . または # からなる長さ $C$ の文字列である．$A_i$ の $j$ 文字目 ($1 \le j \le C$) はマス $(i, j)$ の色を表し，. はそのマスの色が白であることを，# はそのマスの色が黒であることを表す．

출력

標準出力に，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようにするための操作回数の最小値を 1 行で出力せよ．

제한

• $1 \le N \le R \le C$．
• $R \times C \le 6\,000\,000$．
• $1 \le S_r \le R$．
• $1 \le S_c \le C$．
• $1 \le G_r \le R$．
• $1 \le G_c \le C$．
• $(S_r, S_c) \ne (G_r, G_c)$．
• $A_i$ ($1 \le i \le 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 \le 1\,500\,000$．
2. ($19$ 점) $R \times C \le 1\,000$．
3. ($16$ 점) 答えは $10$ 以下である，$R \times C \le 1\,500\,000$．
4. ($19$ 점) $R \times C \le 60\,000$．
5. ($5$ 점) $R \times C \le 150\,000$．
6. ($19$ 점) $R \times C \le 1\,500\,000$．
7. ($8$ 점) $R \times C \le 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 回も行わなくても，白いマスのみを通ってスタートからゴールへ移動する経路が存在する場合がある．

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