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

$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

The first line contains three positive integers $N$, $M$, and $K$. The next $N$ lines each contain $M$ integers representing the matrix $A$, where the $j$-th number in the $i$-th line is $A[i, j]$. The following $K$ lines each contain four integers representing the queries, where the $i$-th line contains $u_{i,1}$, $v_{i,1}$, $u_{i,2}$, and $v_{i,2}$.

Output

The output should contain $K$ lines. The $i$-th line should contain a single integer, which is the answer to the $i$-th query, representing the number of 2D inversions satisfying the corresponding conditions.

Examples

Input 1

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

Output 1

0
4
19