Vus the Cossack and a Field

题意翻译

我们定义一个 $01$ 矩阵 $a$，$01$ 矩阵 $b$ 为 $a$ 翻转后的矩阵（$0$ 变 $1$，$1$ 变 $0$）。 我们定义一个矩阵的一次变幻为把矩阵 $a$ 变成矩阵 $\begin{matrix} a & b & \\ b & a & \\ \end{matrix}$。 例如：原矩阵为：$ \begin{matrix} 1 & 0 & \\ 1 & 1 & \\ \end{matrix} $ 变幻后变成：$ \begin{matrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{matrix} $ 再变幻一次变成：$ \begin{matrix} 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0& 0 & 0 & 0 & 1 & 1 \\ \end{matrix} $ 现在我们将原矩阵变幻无数次，现在有 $q$ 次询问，每次询问四个数 $(x_1,y_1,x_2,y_2)$，你需要回答以 $(x_1,y_1)$ 为左上角 $(x_2,y_2)$ 为右下角的矩阵内的数的和。

题目描述

Vus the Cossack has a field with dimensions $ n \times m $ , which consists of "0" and "1". He is building an infinite field from this field. He is doing this in this way: 1. He takes the current field and finds a new inverted field. In other words, the new field will contain "1" only there, where "0" was in the current field, and "0" there, where "1" was. 2. To the current field, he adds the inverted field to the right. 3. To the current field, he adds the inverted field to the bottom. 4. To the current field, he adds the current field to the bottom right. 5. He repeats it. For example, if the initial field was: $ \begin{matrix} 1 & 0 & \\ 1 & 1 & \\ \end{matrix} $ After the first iteration, the field will be like this: $ \begin{matrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{matrix} $ After the second iteration, the field will be like this: $ \begin{matrix} 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0& 0 & 0 & 0 & 1 & 1 \\ \end{matrix} $ And so on... Let's numerate lines from top to bottom from $ 1 $ to infinity, and columns from left to right from $ 1 $ to infinity. We call the submatrix $ (x_1, y_1, x_2, y_2) $ all numbers that have coordinates $ (x, y) $ such that $ x_1 \leq x \leq x_2 $ and $ y_1 \leq y \leq y_2 $ . The Cossack needs sometimes to find the sum of all the numbers in submatrices. Since he is pretty busy right now, he is asking you to find the answers!

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , $ q $ ( $ 1 \leq n, m \leq 1\,000 $ , $ 1 \leq q \leq 10^5 $ ) — the dimensions of the initial matrix and the number of queries. Each of the next $ n $ lines contains $ m $ characters $ c_{ij} $ ( $ 0 \leq c_{ij} \leq 1 $ ) — the characters in the matrix. Each of the next $ q $ lines contains four integers $ x_1 $ , $ y_1 $ , $ x_2 $ , $ y_2 $ ( $ 1 \leq x_1 \leq x_2 \leq 10^9 $ , $ 1 \leq y_1 \leq y_2 \leq 10^9 $ ) — the coordinates of the upper left cell and bottom right cell, between which you need to find the sum of all numbers.

输出格式

For each query, print the answer.

输入输出样例

输入样例 #1

2 2 5
10
11
1 1 8 8
2 4 5 6
1 2 7 8
3 3 6 8
5 6 7 8

输出样例 #1

32
5
25
14
4

输入样例 #2

2 3 7
100
101
4 12 5 17
5 4 9 4
1 4 13 18
12 1 14 9
3 10 7 18
3 15 12 17
8 6 8 12

输出样例 #2

6
3
98
13
22
15
3

说明

The first example is explained in the legend.