### 问题描述 小 $L$ 有一个 $n$ 行 $m$ 列的矩阵，矩阵里的元素都是 $0$ 或 $1$。小 $L$ 称一个子矩阵是**好的**当且仅当该子矩阵内的元素全为 $0$。 现在小 $L$ 想问你 $q$ 个问题，每个问题都形如：这个矩阵的某个子矩阵有多少个子矩阵是**好的**。 ### 输入格式 第一行有三个正整数 $n, m, q$，分别表示矩阵的行数和列数，以及询问的个数。 接下来 $n$ 行，每行有一个长度为 $m$ 的字符串，表示整个矩阵。 接下来 $q$ 行，每行有四个数 $x_1, y_1, x_2, y_2$，表示询问左上角为 $(x_1, y_1)$，右下角为 $(x_2, y_2)$ 的子矩阵有多少个子矩阵是**好的**。 ### 输出格式 输出共 $q$ 行，每一行表示一个询问的答案。 ### 样例输入 ``` 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 ``` ### 数据范围 对于 $20\\%$ 的数据，满足 $n, m \leq 10, q \leq 100$。 对于 $50\\%$ 的数据，满足 $1 \leq n \leq 50, 1 \leq m \leq 50, 1 \leq q \leq 100$。 另有 $10\\%$ 的数据，满足矩阵的元素全为 $0$。 另有 $20\\%$ 的数据，满足矩阵最多只有 $3$ 个元素为 $1$。 对于 $100\\%$ 的数据，满足 $1\leq n, m \leq 70, 1 \leq q \leq 300,000$。