#include using namespace std; using lint = long long; template using V = vector; template using VV = V< V >; struct Edge { int to, cost; }; template V dijkstra(const VV& g, int s = 0) { V dist(g.size(), numeric_limits::max()); using P = pair; priority_queue< P, V

, greater

> pque; pque.emplace(dist[s] = 0, s); while (!pque.empty()) { T d; int v; tie(d, v) = pque.top(); pque.pop(); if (d > dist[v]) continue; for (const auto& e : g[v]) if (dist[v] + e.cost < dist[e.to]) { pque.emplace(dist[e.to] = dist[v] + e.cost, e.to); } } return dist; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int h, w; cin >> h >> w; int gi, gj; cin >> gi >> gj, --gi, --gj; auto in = [&](int i, int j) -> int { return i * w + j; }; auto out = [&](int i, int j) -> int { return (h + i) * w + j; }; VV g(2 * h * w); VV<> a(h, V<>(w)); for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { cin >> a[i][j]; g[in(i, j)].emplace_back(Edge{out(i, j), a[i][j]}); for (int di = -1; di <= 1; ++di) for (int dj = -1; dj <= 1; ++dj) if (abs(di) + abs(dj) == 1) { int ni = i + di, nj = j + dj; if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue; g[out(i, j)].emplace_back(Edge{in(ni, nj), 0}); } } int q; cin >> q; struct Q { int t, i, j, k; }; V qs(q); for (int t = 0; t < q; ++t) { qs[t].t = t; cin >> qs[t].i >> qs[t].j >> qs[t].k, --qs[t].i, --qs[t].j; } sort(begin(qs), end(qs), [](const auto& l, const auto& r) { return l.k < r.k; }); V res(q); auto itr = begin(qs); while (itr != end(qs)) { lint k = itr->k; if (k >= 2500) { for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { g[in(i, j)][0].cost = a[i][j] + 2500 * 2500; } auto d = dijkstra(g, in(gi, gj)); while (itr != end(qs)) { int dist = abs(itr->i - gi) + abs(itr->j - gj) + 1; res[itr->t] = d[out(itr->i, itr->j)] + dist * ((lint)itr->k * itr->k - 2500 * 2500); ++itr; } break; } for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { g[in(i, j)][0].cost = a[i][j] + k * k; } auto d = dijkstra(g, in(gi, gj)); while (itr != end(qs) and itr->k == k) { res[itr->t] = d[out(itr->i, itr->j)]; ++itr; } } for (lint e : res) cout << e << '\n'; }