#9. 小珅的棋局
小珅的棋局
说明
小珅和朋友正在玩一个游戏,初始时,在一个 n×m 的棋盘上放置着 n×m 个棋子,每枚棋子都有一定的价值,第 i(1≤i≤n) 行第 j(1≤j≤m) 列的棋子的价值为 vi,j。
该游戏的规则为:在棋盘中任意选取两个正方形区域(第 k(1≤k≤2) 个正方形的左上角格子在第 xk 行第 yk 列,边长为 lenk),要求双方玩家使用最短的时间计算出这两个正方形区域中的总价值,谁先计算出正确结果,本局游戏就是谁获胜。
现在小珅想要知道,在他制定的规则下,游戏一共进行 q 局,每局游戏的正确结果是多少,以便于用来核对双方玩家计算出的结果是否正确。
输入格式
第一行,包含两个整数 n,m。
接下来 n 行,每行包含 m 个整数 vi,1,vi,2,…,vi,m。
接下来一行,包含一个整数 q。
接下来 q 行,每行包含 6 个整数 x1,y1,len1,x2,y2,len2。
输出格式
共 t 行,每行一个整数,表示答案。3 4
1 2 3 4
-1 -2 -3 -4
6 7 -6 -7
3
1 1 2 2 3 2
1 1 3 2 2 1
1 1 2 2 2 2-20
7
-2
提示
样例 解释:
游戏第 1 局,选择的两个正方形如下图所示(分别用红色和蓝色框起来的两个正方形),其正确的结果为 −20:
游戏第 2 局,选择的两个正方形如下图所示(分别用红色和蓝色框起来的两个正方形),其正确的结果为 7:
游戏第 3 局,选择的两个正方形如下图所示(分别用红色和蓝色框起来的两个正方形),其正确的结果为 −2:
【数据范围】
对于 40% 数据保证:保证两个正方形区域没有公共区域。
对于 100% 数据保证:1≤xi+leni−1≤n≤800,1≤yi+leni−1≤m≤800,−106≤vi,j≤106,1≤q≤100。