#include #include #include #include using namespace std; typedef long long ll; ll dp[251][251][701] = {}; ll inf = 1e18; int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1}; int main(){ int H,W,gx,gy; cin >> H >> W >> gx >> gy; int K = min(H*W,700); vector> A(H+1,vector(W+1,0)); for(int i=1;i<=H;i++) for(int j=1;j<=W;j++){ cin >> A[i][j]; for(int k=0;k<=K;k++) dp[i][j][k] = inf; } dp[gx][gy][1] = A[gx][gy]; auto in = [&](int x,int y){ return 1<=x && x<=H && 1<=y && y<=W; }; for(int k=1;k> Q; vector ans(Q,0); struct query{ int id,x,y; ll level; bool operator<(const query& right)const{ return level> ans_id(H+1,vector(W+1,K)); vector> ans_now(H+1,vector(W+1,inf)); vector qs; for(int i=1;i<=H;i++) for(int j=1;j<=W;j++){ if((abs(i-gx)+abs(j-gy))%2==1) ans_id[i][j] = K-1; } for(int q=0;q> x >> y >> k; qs.push_back({q,x,y,k}); } sort(qs.begin(),qs.end()); for(auto q:qs){ ans_now[q.x][q.y] = dp[q.x][q.y][ans_id[q.x][q.y]]+ans_id[q.x][q.y]*q.level*q.level; while(ans_id[q.x][q.y]>=2 && ans_now[q.x][q.y]>dp[q.x][q.y][ans_id[q.x][q.y]-2]+(ans_id[q.x][q.y]-2)*q.level*q.level){ ans_now[q.x][q.y] = dp[q.x][q.y][ans_id[q.x][q.y]-2]+(ans_id[q.x][q.y]-2)*q.level*q.level; ans_id[q.x][q.y] -= 2; } ans[q.id] = ans_now[q.x][q.y]; } for(auto x:ans) cout << x << endl; }