Description

Given an $N \times M$ integer matrix $\{A[i,j]\}$ ($1 \le i \le N$, $1 \le j \le M$). You need to answer $K$ queries. The $i$‑th query asks you to count the number of 2D inversion pairs $(x_1, y_1, x_2, y_2)$ that satisfy all of the following:

• $u_{i,1} \le x_1 \le x_2 \le u_{i,2}$,
• $v_{i,1} \le y_1 \le y_2 \le v_{i,2}$,
• $A[x_1, y_1] > A[x_2, y_2]$.

Input Format

This is an answer-submission problem. The input files are named rev1.in ~ rev10.in.

For each rev*.in, the first line contains three positive integers $N, M, K$.

The next $N$ lines each contain $M$ integers, giving the matrix $A$, where the $j$‑th number in the $i$‑th line is $A[i, j]$. Then the next $K$ lines each contain four integers describing the queries; in the $i$‑th of these lines, the four integers are $u_{i,1}, v_{i,1}, u_{i,2}, v_{i,2}$.

Output Format

On Luogu, output a single integer: the XOR of all $K$ answers (i.e., the XOR of the answers to all queries).

Note: The sample is only for understanding the problem and is not the final output format.

(Original answer-submission format for each rev*.out: it contains $K$ lines, where the $i$‑th line is the answer to the $i$‑th query, i.e., the number of 2D inversion pairs that satisfy the corresponding conditions.)

3 5 3
1 2 3 4 5
9 9 9 9 9
1 4 3 5 2
1 1 2 5
3 1 3 5
2 1 3 5

0
4
19

Hint

Please keep the input files *.in and your outputs *.out safe and back them up in time to avoid accidental deletion.

Translated by ChatGPT 5