Swing要开煎饼厂了!一个好的煎饼工厂必须擅长把东西压平,所以 Swing 打算在 2D 矩阵上测试他的新设备。
Swing 被赋予一个包含正整数的 $$$n \times n$$$ 矩阵 $$$M$$$。他有 $$$q$$$ 问题要问你。
对于每个查询,他都会给你四个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$、$$$y_2$$$ 并要求你将 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 边界的子矩阵展平为一个数组$$$A$$$。形式上,$$$A = [M_{(x1,y1)}, M_{(x1,y1+1)}, \ldots, M_{(x1,y2)}, M_{(x1+1,y1)}, M_{(x1+1,y1+1)}, \ldots, M_{(x2,y2)}]$$$。
下图描绘了由红色虚线界定的子矩阵的展平。橙色箭头表示子矩阵的元素附加到$$$A$$$后面的方向,$$$A$$$显示在图像的底部。
然后,他询问你 $$$\sum_{i=1}^{|A|} A_i \cdot i$$$ 的值($$$A_i \cdot i$$$ 与所有 $$$i$$$ 的总和)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。
每个测试的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 2000, 1 \leq q \leq 10^6$$$) — $$$M$$$ 的长度和查询数量。
以下 $$$n$$$ 行每行包含 $$$n$$$ 个整数,其中第 $$$i$$$ 包含 $$$M_{(i,1)}, M_{(i,2)}, \ldots, M_{(i,n)}$$$ ($$$1 \leq M_{(i, j)} \leq 10^6$$$)。
以下 $$$q$$$ 行包含四个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$ 和 $$$y_2$$$ ($$$1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$$$) —查询。
保证所有测试用例的$$$n$$$总和不超过$$$2000$$$,所有测试用例的$$$q$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,在新行中输出 $$$q$$$ 查询的结果。
示例
输入 #1
2 4 3 1 5 2 4 4 9 5 3 4 5 2 3 1 5 5 2 1 1 4 4 2 2 3 3 1 2 4 3 3 3 1 2 3 4 5 6 7 8 9 1 1 1 3 1 3 3 3 2 2 2 2
输出 #1
500 42 168 14 42 5
注意
在第一个测试用例的第二个查询中,$$$A = [9, 5, 5, 2]$$$。因此,总和为 $$$1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42$$$。