题目描述

声明：本题为原题转载及翻译，若侵犯了您的合法权益，请与本站联系，我们将删除题目。

原题链接

Nuske 有一个 $N$ 行 $M$ 列的方形网格。行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。网格中的每个单元格都涂成蓝色或白色。如果 $S{i,j}=1$，则第 $i$ 行第 $j$ 列的单元格为蓝色；如果 $S{i,j}=0$，则单元格为白色。对于每对蓝色单元格 $a$ 和 $b$，最多存在一条每步移动到相邻（有公共边）的蓝色单元格，且不重复经过同一个单元格的，从 $a$ 开始到达 $b$ 的路径。

Nuske 永恒的对手 Phantom Thnook 向 Nuske 发出了 $Q$ 次查询。第 $i$ 次查询由四个整数 $x{i,1},y{i,1},x{i,2},y{i,2}$ 描述，表示询问：如果从网格中分离出第 $x{i,1}$ 到 $x{i,2}$ 行、第 $y{i,1}$ 到 $y{i,2}$ 列的部分，在该区域有几个由蓝色单元格组成的四联通块？

请你回答所有查询。

输入格式

输入从标准输入流按以下形式给出：

$N$　$M$　$Q$
$S{1,1} \cdots S{1,M}$
$\vdots$
$S{N,1} \cdots S{N,M}$
$x{1,1}$　$y{1,1}$　$x{1,2}$　$y{1,2}$
$\vdots$
$x{Q,1}$　$y{Q,1}$　$x{Q,2}$　$y{Q,2}$

输出格式

对于每个询问，输出一行一个整数表示该区域内由蓝色单元格组成的四联通块个数。

样例 1

input

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

output

3
2
2
2

第一次查询了整个网格。有三个蓝色单元格组成的四联通块，因此应该输出 $3$。 第二次查询了红框内的区域。有两个蓝色单元格组成的四联通块，因此应该输出 $2$。请注意，在原始网格中属于相同四联通块的单元格在查询中形可能属于不同的四联通块。

样例 2

input

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

output

3
2
1
1
3
2

数据范围与提示

对于所有数据：

• $1\le N,M\le 2000$
• $1\le Q\le 200000$
• $S_{i,j}\in {0,1}$，且满足题目条件
• $1\le x{i,1}\le x{i,2}\le N(1\le i\le Q)$
• $1\le y{i,1}\le y{i,2}\le M(1\le i\le Q)$