时空限制

1.5S/512M

题目描述

地图可以视为一个 $n\times m$ 的矩阵，称矩阵从上到下第 $i$ 行从左到右第 $j$ 列的格子为 $(i,j)$，分数为 $C_{i,j}$。

如果在 $(i,j)$ 引爆一个爆炸范围为 $w$ 的炸弹，会炸到满足 $|x-i|+|y-j|\leq w$ 的任意格子 $(x,y)$，包括 $(i,j)$ 本身。炸弹爆炸的总分数为炸到的所有格子的分数之和，爆炸并不会对矩阵产生影响。

有 $q$ 个询问，第 $i$ 个询问求如果在 $(x_i,y_i)$ 引爆一个爆炸范围为 $w_i$ 炸弹，这次爆炸总分数是多少。

由于输入/输出的数据量可能很大，因此建议使用更快速的输入/输出方法：例如，在 C++ 语言下使用 scanf/printf 而不是 cin/cout，在 Java 语言下使用 BufferedReader/PrintWriter 而不是 Scanner/System.out。

格式

输入格式

第一行包含三个整数 $n,m,q$，分别表示矩阵的行数和列数，以及询问的数量。

接下来 $n$ 行每行 $m$ 个整数，其中第 $i$ 行第 $j$ 列的整数 $C_{i,j}$ 表示格子 $(i,j)$ 的分数。

接下来 $q$ 行每行三个整数 $x_i,y_i,w_i$，表示询问在 $(x_i,y_i)$ 引爆一个爆炸范围为 $w_i$ 炸弹，这次爆炸总分数是多少。

输出格式

对于每个询问，在单独的一行中输出一个整数表示答案。

样例

样例输入 #1

4 6 3
1 2 3 4 5 6
6 5 4 3 2 1
1 2 4 8 16 32
1000000 100000 10000 1000 100 10
1 2 3
3 2 0
1 1 1000

样例输出 #1

100040
2
1111215

数据规模

对于 $30\%$ 的数据，$w_i\leq 5$。

另有 $30\%$ 的数据，$q\leq 10^5$，$w_i\leq 500$。

对于 $100\%$ 的数据，$1\leq n,m\leq 1000$，$1\leq q\leq 10^6$，$1\leq C_{i,j}\leq 10^9$，$1\leq x_i\leq n$，$1\leq y_i\leq m$，$0\leq w_i\leq 1000$。