#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) REP(i,0,n) using ll = long long; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; struct query{ ll sx,sy,id,k; }; signed main(){ int h,w; cin>>h>>w; ll a[h][w]; int gx,gy; cin>>gx>>gy; --gx;--gy; rep(i,h)rep(j,w)cin>>a[i][j]; int q; cin>>q; vector v[161]; rep(i,q){ int x,y,k; cin>>x>>y>>k; --x;--y; v[min(k,300ll)].push_back({x,y,i,k}); } ll dist[h][w]; int di[]={1,0,-1,0,1}; vector ans(q); rep(K,301){ if(v[K].empty())continue; rep(i,h)rep(j,w){ dist[i][j]=longinf; } dist[gx][gy]=K*K+a[gx][gy]; using T =pair>; priority_queue, greater> pq; pq.push({dist[gx][gy],{gx,gy}}); while(pq.size()){ ll d = pq.top().first; auto p = pq.top().second; pq.pop(); int x = p.first, y = p.second; if(dist[x][y]=h||ny<0||ny>=w)continue; if(dist[nx][ny]>d+a[nx][ny]+K*K){ dist[nx][ny]=d+a[nx][ny]+K*K; pq.push({dist[nx][ny],{nx,ny}}); } } } for(auto Q :v[K]){ ans[Q.id]=dist[Q.sx][Q.sy]; if(K!=Q.k){ ll d = abs(Q.sx-gx)+(Q.sy-gy)+1; ans[Q.id]+=(Q.k*Q.k-K*K)*d; } } } for(auto e : ans)cout<