Tyl 准备了一个尺寸为 n*m（一共 n 行，每行 m 个格子）的棋盘，并在棋盘的每个格子里都放入了一些金币。 用 (x, y) 表示位于第 x 行第 y 列的格子，两个格子 (a, b) 和 (c, d) 的距离定义为 abs(a-c)+abs(b-d) 现在 Tyl 准备问你 q 个问题，对于每一个问题，给定 x,y,k ，请你求出离 (x, y) 距离不超过 k 的所有格子里的金币总和是多少。
输入描述:
第一行是一个整数 T(1<=T<=100)，表示数据组数。
对于每一组数据：
第一行是 2 个整数 n,m(1<=n,m<=1000) ，表示棋盘的尺寸。
接下来一共 n 行，每行 m 个整数，用以表示棋盘内每个格子放入的金币数量，每个格子内放入的金币数量 v 满足 (1<=v<=1000000)。
接下来 1 个整数 q(1<=q<=100000) 表示询问个数。
接下来一共 q 行，每行 3 个整数 x,y,k(1<=x<=n, 1<=y<=m, 1<=k<=max(n,m)) 表示一组询问。
输出描述:
对于每一个询问 x,y,k ，输出一行包括一个数字表示离 (x,y) 距离不超过 k 的所有格子里的金币总和是多少。
示例1
输入
复制
1
3 4
1 2 3 4
5 6 7 8
9 10 11 12
4
2 2 0
2 2 1
2 2 2
2 2 3