站外题。
题面：
有一个 $n \times m$ 的矩阵，第 $i$ 行 $j$ 列的坐标是 $(i,j)$ 。每个元素有元素值。有 $q$ 次询问。每次给三个数 $x,y,k$ ，求与坐标 $(x,y)$ 曼哈顿距离小于k的哥子元素值。
数据：
$n=m=1000,q=300000$
感觉得前缀和，关键是怎么写啊！ 我的代码也就这样：

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int x,y,k;
		cin>>x>>y>>k;
		if(k==1)cout<<a[x][y]<<endl;
		else{
			int ans=0;
			for(int j=1;j<=n;j++){
				for(int k=1;k<=m;k++){
					if(abs(i-x)+abs(j-y)<k){
						ans+=a[i][j];
					}
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

有人能给我一个思路或者告诉我应该怎样写吗？ orz