Counting 2D Inversion Pairs in a Submatrix

Given an $N \times M$ integer matrix $\{A[i,j]\}$ ($1 \leq i \leq N$, $1 \leq j \leq M$), answer $K$ queries. For the $i$-th query, count the number of 2D inversion pairs $(x_1, y_1, x_2, y_2)$ satisfying the conditions:

Note that the indices of the matrix are 1-indexed.

inputFormat

The first line contains three integers $N$, $M$, and $K$, representing the number of rows, the number of columns of the matrix, and the number of queries, respectively.

The next $N$ lines each contain $M$ integers, where the $j$-th integer on the $i$-th line represents $A[i,j]$.

Each of the following $K$ lines contains four integers $u_{i,1}$, $u_{i,2}$, $v_{i,1}$, and $v_{i,2}$, describing a query that asks for the number of inversion pairs in the submatrix with rows from $u_{i,1}$ to $u_{i,2}$ and columns from $v_{i,1}$ to $v_{i,2}$.

outputFormat

For each query, print one line containing a single integer representing the number of inversion pairs in the specified submatrix.

sample

3 3 2
1 2 3
4 5 6
7 8 9
1 2 1 2
2 3 2 3

0
0