题目描述

小珅和朋友正在玩一个游戏，初始时，在一个 $n\times m$ 的棋盘上放置着 $n\times m$ 个棋子，每枚棋子都有一定的价值，第 $i(1\le i\le n)$ 行第 $j(1\le j\le m)$ 列的棋子的价值为 $v_{i,j}$。

该游戏的规则为：在棋盘中任意选取两个正方形区域（第 $k(1\le k\le 2)$ 个正方形的左上角格子在第 $x_k$ 行第 $y_k$ 列，边长为 $len_k$），要求双方玩家使用最短的时间计算出这两个正方形区域中的总价值，谁先计算出正确结果，本局游戏就是谁获胜。

现在小珅想要知道，在他制定的规则下，游戏一共进行 q 局，每局游戏的正确结果是多少，以便于用来核对双方玩家计算出的结果是否正确。

输入格式

第一行，包含两个整数 n,m。

接下来 n 行，每行包含 m 个整数 $v_{i,1}$,$v_{i,2}$,…,$v_i$,m。

接下来一行，包含一个整数 q。

接下来 q 行，每行包含 6 个整数 $x_{1}$,$y_{1}$,len1,$x_{2}$,$y_{2}$,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

提示

样例 2 解释：

游戏第 1 局，选择的两个正方形如下图所示（分别用红色和蓝色框起来的两个正方形），其正确的结果为 −20：

游戏第 2 局，选择的两个正方形如下图所示（分别用红色和蓝色框起来的两个正方形），其正确的结果为 7：

游戏第 3 局，选择的两个正方形如下图所示（分别用红色和蓝色框起来的两个正方形），其正确的结果为 −2：

数据范围

对于 40% 数据保证：保证两个正方形区域没有公共区域。

对于 100% 数据保证：$1\le x_i+len_i-1\le n\le 800,1\le y_i+len_i-1\le m\le 800,-10^{6}\le v_{i,j}\le 10^{6},1\le q\le 100$。

1 1
-1000000
1
1 1 1 1 1 1

-1000000

2 2
1000000 -1000000
-1000000 1000000
2
1 1 2 1 1 2
1 1 1 2 2 1

0
2000000

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