Colmerauer

Peter has an $n \times m$ matrix $M$. Let $S(a,b)$ be the sum of the weight all $a \times b$ submatrices of $M$. The weight of matrix is the sum of the value of all the saddle points in the matrix. A saddle point of a matrix is an element which is both the only largest element in its column and the only smallest element in its row. Help Peter find out all the value of $S(a,b)$.

Note: the definition of saddle point in this problem may be different with the definition you knew before.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first contains two integers $n$ and $m$ $(1 \le n, m \le 1000)$ -- the dimensions of the matrix.

The next $n$ lines each contain $m$ non-negative integers separated by spaces describing rows of matrix $M$ (each element of $M$ is no greater than $10^6$).

For each test case, output an integer $W = (\displaystyle\sum_{a=1}^{n}\sum_{b=1}^{m}{a \cdot b \cdot S(a,b)}) \text{ mod } 2^{32}$.

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

4
600
215

BestCoder Round #84