Problem Description

There is an $N\times M$ grid. Rows and columns are numbered starting from $0$, and cells are indexed from the top-left to the bottom-right.

The cell in row $i$ and column $j$ is black if and only if $i\text{ and }j=0$.

Two black cells are connected if and only if they are both black and one can reach the other by passing through some black cells, where each step moves between black cells that share a common edge.

You are given $Q$ rectangles, with top-left corner $(x_1,y_1)$ and bottom-right corner $(x_2,y_2)$. For each rectangle, you need to find how many connected components are formed by all black cells inside it.

Input Format

The first line contains three integers $N,M,Q$, representing the grid size and the number of queries.

The next $Q$ lines each contain four integers $x_1,y_1,x_2,y_2$, representing a query rectangle.

Output Format

For each query, output one line containing one integer, representing the answer.

6 5 4
0 0 3 2
0 2 1 3
0 1 2 4
5 4 5 4

1
1
2
0

Hint

[Sample Explanation]

The following figures illustrate the four queries in the sample:

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (5 points): There is only one test case, with $N = M=12$, $Q=3$, and the queried $(x_1,y_1,x_2,y_2)$ are, in order, $(1,1,9,8)$, $(8,8,11,11)$, and $(4,3,5,9)$.
• Subtask 2 (11 points): $N,M,Q\le 200$.
• Subtask 3 (10 points): $N,M,Q\le 2000$, $x_1=x_2$.
• Subtask 4 (20 points): $N,M,Q\le 2000$.
• Subtask 5 (4 points): $x_1=x_2=0$.
• Subtask 6 (6 points): For each query, it is guaranteed that there exists an integer $k$ such that $x_1=x_2=2^k$.
• Subtask 7 (29 points): $x_1=x_2$.
• Subtask 8 (15 points): No special restrictions.

For all testdata, $0\leq x_1\leq x_2<N\leq 10^9$, $0\leq y_1\leq y_2<M\leq 10^9$, $1\leq Q\leq 10^5$.

Translated by ChatGPT 5