题目描述

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

输入

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

样例 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