問題文

この問題はEasyとHardのバージョンがあります。問題文は同じで、赤字で示された制約が異なります。
この問題はHard版です。
なお、Easy版の解法を提出した場合、99%の部分点が入ります。おまけとして捉えていただければ幸いです。
部分点は削除となりました。

$H \times W$ の大きさのクロスワードがあります。
フレロビくんはクロスワードを作りましたが、一部分だけ見るとカギがいくつなのか気になりました。

$H \times W$ の盤面が、 $H$ 個の文字列 $S_1,S_2,\cdots,S_H$ によって与えられます。
上から $i$ 番目、左から $j$ 番目のマスは、 $S_i$ の $j$ 文字目が # の場合は黒マス、 . の場合は白マスです。

$Q$ 個のクエリが与えられるので、指定された範囲のみをクロスワードとして見たときに存在するカギの数を求めてください。
具体的には、上から $i$ 番目、左から $j$ 番目のマスを、$(i,j)$ と表すことにしたとき、$(A,B)$ から $(C,D)$ までの長方形領域に含まれるマスを盤面として、そのクロスワードにおけるカギの添字の最大値を求めてください。

ただし、カギのある位置は次の条件のいずれかを満たすものとします。

• 横のカギ: そのマスが白マスかつ、そのマスの左が黒マスまたは盤面の外であり、そのマスの右が白マスである。
• 縦のカギ: そのマスが白マスかつ、そのマスの上が黒マスまたは盤面の外であり、そのマスの下が白マスである。

なお、次のような条件を満たすものもカギであるとします。

• 1マスカギ: そのマスが白マスかつ、そのマスの上下左右が黒マスまたは盤面の外である。

横のカギと縦のカギが重複する場合があることに注意してください。その場合はどちらも同じ添字を使います。
また、カギの添字は1から始まり、盤面の上側の方が小さく、同じ行では左側が小さいものとします。
カギの数は、カギの添字の最大値に等しいです。

制約

• $2 \le H,W \le\ $$600$
• $1 \le Q \le\ $$600,000$
• $1 \le A \le C \le H$
• $1 \le B \le D \le W$
• $S_i$ は # または . で構成される長さ $W$ の文字列
• $H,W,Q,A,B,C,D$は整数

入力

$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

各 $query$ は、次の形式で与えられます。

$A\ B\ C\ D$

出力

$Q$ 行出力してください。 $i$ 行目には、 $i$ 番目のクエリに対する答えを出力してください。

最後に改行してください。

サンプル

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

1
1

##
#.

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

3
3
2
0