配点 : $700$ 点

問題文

ぬすけ君は、$N \times M$ のグリッドを持っています。行には上から順に $1$ から $N$、列には左から順に $1$ から $M$ の番号がついています。 グリッドの各マスは白か青かに塗られており、$S_{i,j}$ が $1$ のとき $i$ 行 $j$ 列のマスは青マス、$0$ のとき白マスです。 青く塗られた任意の二つのマス $a,b$ について、$a$ からはじめて、現在いるマスから辺を共有する青いマスに進むことを繰り返して $b$ に至るような経路のうち、同じマスを $2$ 度以上通らないようなものは、高々 $1$ 通りです。

ぬすけ君の永遠のライバルである怪盗スヌークは、ぬすけ君に $Q$ 個の質問をしました。$i$ 個目の質問は、$4$ つの整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ からなり、 グリッドの $x_{i,1}$ 行目から $x_{i,2}$ 行目まで、$y_{i,1}$ 列目から $y_{i,2}$ 列目までの範囲の長方形領域を切り出したときに、 その範囲の青マスからなる連結成分がいくつあるかを答える質問です。

怪盗スヌークの質問すべてに答えてください。

制約

• $1 \leq N,M \leq 2000$
• $1 \leq Q \leq 200000$
• $S_{i,j}$ は $0$ または $1$ である
• $S_{i,j}$ は問題文中の条件を満たす
• $1 \leq x_{i,1} \leq x_{i,2} \leq N(1 \leq i \leq Q)$
• $1 \leq y_{i,1} \leq y_{i,2} \leq M(1 \leq i \leq Q)$

入力

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

$N$ $M$ $Q$

$S_{1,1}$..$S_{1,M}$

:

$S_{N,1}$..$S_{N,M}$

$x_{1,1}$ $y_{i,1}$ $x_{i,2}$ $y_{i,2}$

:

$x_{Q,1}$ $y_{Q,1}$ $x_{Q,2}$ $y_{Q,2}$

出力

質問ごとに、その範囲の青マスからなる連結成分がいくつあるかを出力せよ。

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

3
2
2
2

$1$ つ目の質問では、グリッド全体が指定されます。青マスからなる連結成分は $3$ つあるので、$3$ を出力します。

$2$ つめの質問では、赤枠の範囲が指定されます。青マスからなる連結成分は $2$ つあるので、$2$ を出力します。 もとのグリッドで同じ成分に属するマスが、異なる成分に属するかもしれないことに注意してください。

5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4

3
2
1
1
3
2