問題文
人気のゲーム「壊れた出口」は、最小の移動回数で迷路から脱出することを目指すパズルゲームです。
迷路は、$N \times M$ 個のマスからなり、各マスには行番号と列番号が割り当てられています。
行番号が $r$、列番号が $c$ のマスは$(r, c)$で表します。左上隅がマス$(0, 0)$、右下隅がマス$(N-1, M-1)$です。
各マスには以下のいずれかの記号が割り当てられています。
. 地面
E 出口
# 壁
ゲームの各プレイで、あなたはプレイごとに指定されたマスから出発して出口を目指します。各出口へは壁以外のどのマスからもたどり着くことができます。
あなたがいるマスの上下左右の隣接したマスが地面または出口であれば、そのマスに移動することができます。ただし、マスのない場所には移動することはできません。
迷路には$2$つ以上の出口が存在しますが、そのうちの一つが壊れています。どの出口が壊れているかは、プレイごとに指定されます。壊れていない出口にあなたがたどり着いたらプレイ終了です。
出口が壊れていてもその出口のマスに移動することはできますが、プレイ終了にはなりません。
課題
$1$つの迷路と、各プレイの情報が与えられたとき、各プレイが終了するまでの最小移動回数を出力するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$N \ M$
$row_{1}$
$row_{2}$
$\vdots$
$row_{N}$
$P$
$sr_{1} \ sc_{1} \ br_{1} \ bc_{1}$
$sr_{2} \ sc_{2} \ br_{2} \ bc_{2}$
$\vdots$
$sr_{P} \ sc_{P} \ br_{P} \ bc_{P}$
$1$行目に迷路の大きさを表す$2$つの整数$N \ (2 \leq N \leq 1,000)$と$M \ (2\leq M \leq 1,000)$が与えられる。続く$N$行に上から$i$番目に並んだマスの情報を表す文字列$row_{i}$が与えられる。 $row_{i}$は長さ$M$の文字列であり、$j$文字目がマス$(i-1, j-1)$の記号を表す。続く行にプレイの数$P \ (1 \leq P \leq 100,000)$が与えられる。 続く$P$行に各プレイで指定される、出発点である地面のマス$(sr_{i},sc_{i})$、壊れている出口のマス$(br_{i},bc_{i})$を表す整数$sr_{i},sc_{i},br_{i},bc_{i} \ (0 \leq sr_{i},br_{i} \lt N, 0 \leq sc_{i},bc_{i} \lt M)$が与えられる。
出力
出力は $P$ 行である。各プレイに対して最小移動回数を$1$行に出力する。
入出力例
入力例1
4 5 ..... .#.#E ..##. .E... 3 0 0 3 1 1 2 3 1 1 2 1 4
出力例1
5 4 7