#include #include #include #include #define llint long long #define inf 1e18 using namespace std; typedef pair P; typedef pair S; llint h, w, Q; llint sx, sy; llint a[255][255]; llint dist[255][255][255]; llint dp[255][255]; int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; void dijkstra(llint k, llint dist[255][255]) { for(int y = 1; y <= h; y++){ for(int x = 1; x <= w; x++){ dist[x][y] = inf; } } dist[sx][sy] = a[sx][sy]+k*k; priority_queue< S, vector, greater > Q; Q.push( make_pair(a[sx][sy]+k*k, make_pair(sx, sy)) ); llint x, y, d, nx, ny; while(Q.size()){ d = Q.top().first; x = Q.top().second.first, y = Q.top().second.second; Q.pop(); if(dist[x][y] < d) continue; for(int i = 0; i < 4; i++){ nx = x + dx[i], ny = y + dy[i]; if(nx < 1 || nx > w || ny < 1 || ny > h) continue; if(dist[nx][ny] > d + a[nx][ny]+k*k){ dist[nx][ny] = d + a[nx][ny]+k*k; Q.push( make_pair(dist[nx][ny], make_pair(nx, ny)) ); } } } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> h >> w; cin >> sy >> sx; for(int y = 1; y <= h; y++){ for(int x = 1; x <= w; x++){ cin >> a[x][y]; } } for(int i = 0; i < 255; i++) dijkstra(i, dist[i]); for(int x = 1; x <= w; x++){ for(int y = 1; y <= h; y++){ dp[x][y] = inf; } } dp[sx][sy] = a[sx][sy]; for(int x = 0; sx+x <= w; x++){ for(int y = 0; sy+y <= h; y++){ int px = sx+x, py = sy+y; if(x > 0) dp[px][py] = min(dp[px][py], dp[px-1][py]); if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py-1]); dp[px][py] += a[px][py]; } } for(int x = 0; sx-x >= 1; x++){ for(int y = 0; sy+y <= h; y++){ int px = sx-x, py = sy+y; if(x > 0) dp[px][py] = min(dp[px][py], dp[px+1][py]); if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py-1]); dp[px][py] += a[px][py]; } } for(int x = 0; sx-x >= 1; x++){ for(int y = 0; sy-y >= 1; y++){ int px = sx-x, py = sy-y; if(x > 0) dp[px][py] = min(dp[px][py], dp[px+1][py]); if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py+1]); dp[px][py] += a[px][py]; } } for(int x = 0; sx+x <= w; x++){ for(int y = 0; sy-y >= 1; y++){ int px = sx+x, py = sy-y; if(x > 0) dp[px][py] = min(dp[px][py], dp[px-1][py]); if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py+1]); dp[px][py] += a[px][py]; } } cin >> Q; llint x, y, k; for(int q = 0; q < Q; q++){ cin >> y >> x >> k; if(k <= 250) cout << dist[k][x][y] <<"\n"; else cout << dp[x][y]+(abs(x-sx)+abs(y-sy)+1)*k*k << "\n"; } flush(cout); return 0; }