Background

Description

liu_runda退役之后就失去梦想开始咸鱼生活了…
Bilibili 夏日画板活动中,所有人都可以在一块画板上进行像素画创作.UOJ群有一群无聊的人决定在画板上创作一个50 * 50的UOJ的LOGO.
这块画板实际上是很大的矩形网格.一个网格是一像素.
一个人每三分钟才能画一个像素.所以liu_runda的咸鱼生活非常无聊.
郭神表示他实在是看不下去 liu_rudna 这只颓狗了,于是随手出了一道神题,liu_runda不会做,于是给出到联考里了.
在画板上有一片黑白相间的矩形区域满足这样的性质:如果认为相同颜色的方块可以在上下左右四个方向连通,那么任意两个黑色方块要么不连通,要么连通但之间只有一条简单路径(不重复经过同一个格子的路径).
这个矩形区域有 N 行M列,从上到下依次为第 1,2,3…N-1,N 行,从左到右依次为第1,2,3…M-1,M列.
每次郭神会询问这片矩形区域内的一个子矩形.在只考虑这个子矩形内的像素时(即从子矩形内部不能和子矩形之外的像素相连通),问这个子矩形内的黑色方块组成了多少连通块.
如果不能完成这个任务,liu_runda就会被郭神批判一番…

Format

Input

第一行三个整数N,M,Q,表示矩形区域有N行M列,有Q组询问.
接下来N 行,每行一个长为 M 的01字符串.0 表示白色,1 表示黑色.第 i 行第 j 个字符表示第i行j列的颜色,
接下来 Q 行,每行 4 个整数 x1,y1,x2,y2,(x1<=x2,y1<=y2)表示选出的矩形区域的两个对角.即选出一个左上角为第x1行第y1列,右下角为第x2行第y2列,包含x2-x1+1行,y2-y1+1列的区域.

Output

Q行,第i行一个整数ans表示第i组询问的答案.

Sample 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

Sample 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 

Limitation

对于第1,2个测试点,Q=1
对于第3,4个测试点,N=1
对于第5,6,7个测试点,N=2
对于第8个测试点,N,M<=1000
对于第9个测试点,N,M<=1500
对于全部测试
点,1<=N,M<=2000,1<=Q<=200000,1<=x1<=x2<=N,1<=y1<=y2<=M,保证任意两个黑色像素之间最多只有一条简单路径.
2s, 512000KiB for each test case.

Hint

Source

CDQZ TEST