Description

某知名选手退役之后就失去梦想开始咸鱼生活了…
Bilibili夏日画板活动中,所有人都可以在一块画板上进行像素画创作.UOJ群有一群无聊的人决定在画板上创作一个50*50的UOJ的LOGO.如下图.

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

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

Limitation

2s, 512MB for each test case.

Hint

对于第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,保证任意两个黑色像素之间最多只有一条简单路径.

Source

高一年级信息学奥赛模拟考(三)