Vus the Cossack and a Field
Contest: Codeforces Round 571 (Div. 2)
Difficulty rating: 2500
Tags: divide and conquer, implementation, math

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!

Input format:
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.

Output format:
For each query, print the answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first example is explained in the legend.

Example input:
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

Example output:
32
5
25
14
4

Example input:
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

Example output:
6
3
98
13
22
15
3

Editorial:
Let's define $$$f(x,y)$$$ a function that returns sum of all elements of submatrix $$$(1,1,x,y)$$$ (these $$$4$$$ numbers stand for $$$x_1, y_1, x_2, y_2$$$ respectively. If we can get value of this function in a fast way, then we can answer the queries quickly by using well known formula for sum on submatrix with cooridantes $$$x_1, y_1, x_2, y_2$$$:
$$$$$$sum = f(x_2,y_2) - f(x_2, y_1 - 1) - f(x_1 - 1, y_2) + f(x_1-1,y_1-1)$$$$$$
If you want to prove the formula you should draw some examples and use the inclusion-exclusion principle.
So we reduced our task to finding value of $$$f(x,y)$$$ for some arbitrary $$$x$$$ and $$$y$$$.
At first, we should precalculate values of $$$f(x,y)$$$ for every $$$1 \le x \le n, 1 \le y \le m$$$. This can be easily done using dynamic programming.
Let's forget about the sums for a while. Let's take a look on the fields. They can be both inverted or not inverted. Let's see how fields are distributed when generating an infinite field.
At step $$$0$$$ we have one field, which is not inverted: $$$$$$\begin{matrix} 0 \\ \end{matrix}$$$$$$
At step $$$1$$$ we have four fields: $$$$$$\begin{matrix} 0 & 1 & \\ 1 & 0 & \\ \end{matrix}$$$$$$
And so on...
After 3 steps we can see that you can split each horizontal or vertical line in pairs of inverted and not inverted fields like on the picture (vertical pairs are highlighted with yellow, horizontal pairs are highlighted with red):
Sum of inverted and not inverted matrices of size $$$n \times m$$$ is equal to $$$n \cdot m$$$.
Knowing these facts we can get $$$O(1)$$$ solution.
Let's say that we want to know $$$f(x,y)$$$. Let's define $$$field_x$$$ and $$$field_y$$$ as coordinates of the field which cell $$$(x,y)$$$ belongs to. They can be easily found: $$$$$$field_x = \Big\lfloor \frac{x-1}{n} \Big\rfloor + 1 $$$$$$ $$$$$$field_y = \Big\lfloor \frac{y-1}{m} \Big\rfloor + 1 $$$$$$
The solution is splited into four parts:
1. When both $$$field_x$$$ and $$$field_y$$$ are odd.
2. When $$$field_x$$$ is odd, but $$$field_y$$$ is even.
3. When $$$field_x$$$ is even, but $$$field_y$$$ is odd.
4. When both $$$feild_x$$$ and $$$field+y$$$ are even.
Solving each of the part is very similar, so I'll show you how to get value of $$$f(x,y)$$$ if both $$$field_x$$$ and $$$field_y$$$ are even (In this particular example $$$field_x = field_y = 4$$$). The big black dot shows us the position of $$$(x,y)$$$ (i.e. it shows that the cell with coordinates $$$(x, y)$$$ is located somewhere in the field with coordinates $$$(4,4)$$$).
Using the fact I mentioned before we can get the value of pairs highlited as red: it is equal to $$$$$$\frac{((field_x - 1) \cdot (field_y - 1) - 1) \cdot n \cdot m}{2}$$$$$$
You can easily use the same fact in order to find the blue and yellow parts.
In order to find the green parts we need to know whether each of the matrices, highlighted with green is inversed. How to know if the matrix with coordinates $$$(a,b)$$$ is inversed? Here is the trick (here $$$bitcnt$$$ is the function which returns number of bits in a number):