AT_agc015_c [AGC015C] Nuske vs Phantom Thnook

Nuske 现在有一个 $N\times M(N,M\le 2000)$ 的矩阵 $S$，若 $S_{i,j}=1$，那么该处为蓝色，否则为白色，保证所有蓝色格子构成的连通块都是树。 给出 $Q(Q\le 200000)$ 次询问, 每次询问一个子矩阵中蓝色连通块的个数。

第一行 三个整数 $N,M,Q$。 接下来 $N$ 行对应矩阵 $S$，每行一个长度为 $M$ 且只包含 $0,1$ 的字符串。 接下来 $Q$ 行, 每行四个整数 $x_1,y_1,x_2,y_2$ 表示相应询问。

共 $Q$ 行, 每行一个整数对应相应询问。

### 制約 - $ 1\ ≦\ N,M\ ≦\ 2000 $ - $ 1\ ≦\ Q\ ≦\ 200000 $ - $ S_{i,j} $ は $ 0 $ または $ 1 $ である - $ S_{i,j} $ は問題文中の条件を満たす - $ 1\ ≦\ x_{i,1}\ ≦\ x_{i,2}\ ≦\ N(1\ ≦\ i\ ≦\ Q) $ - $ 1\ ≦\ y_{i,1}\ ≦\ y_{i,2}\ ≦\ M(1\ ≦\ i\ ≦\ Q) $ ### Sample Explanation 1 !\[\](https://atcoder.jp/img/agc015/7aa4a2252f50a19fc18e0cec01368a2a.png) $ 1 $ つ目の質問では、グリッド全体が指定されます。青マスからなる連結成分は $ 3 $ つあるので、$ 3 $ を出力します。 $ 2 $ つめの質問では、赤枠の範囲が指定されます。青マスからなる連結成分は $ 2 $ つあるので、$ 2 $ を出力します。 もとのグリッドで同じ成分に属するマスが、異なる成分に属するかもしれないことに注意してください。