问题描述
Peter有一个$n \times m$的矩阵$M$. 定义$S(a,b)$为$M$的所有大小为$a \times b$的子矩阵的权值和. 一个矩阵的权值是这个矩阵所有鞍点的值的和. 在矩阵中, 一个数在所在行中是唯一的最小值, 在所在列中是唯一的最大值, 则被称为鞍点. 帮助Peter找出所有$S(a,b)$的值.
注意: 本题中鞍点的定义可能和你所知的有所不同.
输入描述
输入包含多组数据, 第一行包含一个整数$T$表示测试数据组数. 对于每组数据:
第一行包含两个整数$n$和$m$ $(1 \le n, m \le 1000)$表示矩阵的大小.
接下来$n$行每行包含$m$个非负整数, 表示矩阵$M$的每一行 ($M$中每个元素都不超过$10^6$).
输出描述
对于每组数据, 输出一个整数$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
