题目描述

给定一个 $n \times m$ 的 $01$ 矩阵，$q$ 次询问，每次询问指定一个子矩形，求该子矩形种有多少个只包含 $0$ 的子矩阵。

矩阵从上到下编号 $1\sim n$，从左到右编号 $1\sim m$。

输入格式

第一行三个整数 $n,m,q$，$1\le n,m\le 40$，$1\le q\le 3\times 10^5$。

接下来 $n$ 行，每行 $m$ 个整数描述该矩阵。

接下来 $q$ 行，每行四个整数 $a,b,c,d$ 表示询问的子矩阵左上角为 $(a,b)$，右下角为 $(c,d)$。

输出格式

对于每个询问，输出一个整数表示答案。

5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3

10
1
7
34
5

4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7

3
1
16
27
52