说明

徐老师最近学习了《子矩阵和》这道题

题目内容是给出一个 $n * m$ 的矩阵，矩阵中每个格子上都有一个数值，每次询问一个子矩阵的和是多少

但是比起矩形，徐老师更喜欢等腰直角三角形，于是徐老师想知道，如果把题目改成《三角形和》会怎么样

徐老师会给出一个格子的坐标 $(x,y)$ 表示这个等腰直角三角形左上角的点，和这个直角边长 $l$

注意，这里的边长 $l$ 是指这条边覆盖几个格子

例如一个左上角为 $(2,2)$ 边长为 $3$ 的等腰直角三角形，在 $5 * 5$ 的矩阵中表示如下（用 $1$ 表示三角形覆盖的区域）：

```cpp
00000
01000
01100
01110
00000
```

注意，这里给定的坐标是左上角的非直角顶点，所以这个三角形是唯一的

输入格式

一行两个正整数 $n$ 和 $m$。

$n$ 行每行 $m$ 个正整数描述 $n$ 行 $m$ 列的矩阵，第 $i$ 行 $j$ 列的数为 $a_{i,j}$。

一个正整数 $q$ 代表询问次数。

$q$ 行每行三个正整数 $x, y, l$ 意义如题所示。
对于 $30\%$ 的数据，$1 \leq n,m \leq 100, 1 \leq a_{i,j} \leq 10^6, 1 \leq q \leq 100$。

对于 $50\%$ 的数据，$1 \leq n, m \leq 100, 1 \leq a_{i,j} \leq 10^8, 1 \leq q \leq 100$。

对于 $100\%$ 的数据，$1 \leq n, m \leq 1000, 1 \leq a_{i,j} \leq 10^8, 1 \leq q \leq 10^6$。

注意，只保证三角形的直角顶点和左上角定点不会越界，如果三角形有超出矩阵范围的部分，该部分的数按 $0$ 算

输出格式

$q$ 行每行一个正整数代表该等腰直角三角形里所有点权值的和。

样例

5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1
1 1 2

3