Background背景

给出一个 n 行 m 列的矩阵，矩阵的每个位置有一个非负整数 f[i][j]，有 q 次询问，每次询问求一个左上角为 (a,b)，右下角为 (c,d) 的子矩阵的所有数之和。

Input输入

第一行两个整数 n,m，表示矩阵的行和列的大小。 接下来 n 行每行 m 个整数，为矩阵内容。 接下来一行为一个整数 q ，表示询问次数。 接下来 q 行每行 4 个整数 a,b,c,d，含义见题面。

Output输出

共 q 行，第 i 行为第 i 个询问的答案。 数据范围 n ,m, f[i][j] < 300，q < 100,000，1 < a < c < n，1 < b < d < m。

Samples样例

3 5
1 2 3 4 5
3 2 1 4 7
2 4 2 1 2
3
1 1 3 5
2 2 3 3
1 1 3 3

43
9
20

Limitation限制

1s, 1024KiB for each test case.