b.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define uint unsigned int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
const int INF = (int)(1e9 + 7);
const ll INFLL = (ll)(1e18 + 7);
const ld Pi = acos(-1.0);
const ld Eps = (ld)(1e-12);
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
int c[600][600], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
pair <int, int> pr[600][600][30];
ll d[600][600];
vector <pair <int, int> > g[600][600];
void dfs(int x, int y){
    for(int power = 1; power <= 20; power ++){
        pair <int, int> prr = pr[x][y][power - 1];
        pr[x][y][power] = pr[prr.f][prr.s][power - 1];
    }
    for(int i = 0; i < g[x][y].size(); i ++){
        int xx = g[x][y][i].f, yy = g[x][y][i].s;
        dfs(xx, yy);
    }
    return;
}
int main(){
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    //cout.precision(12);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> c[i][j];
            d[i][j] = INFLL;
        }
    }
    set <pair <ll, pair <int, int> > > st;
    for(int i = 1; i <= n; i ++){
        st.insert({c[i][1], {i, 1}});
        d[i][1] = c[i][1];
        st.insert({c[i][m], {i, m}});
        d[i][m] = c[i][m];
    }
    for(int i = 1; i <= m; i ++){
        st.insert({c[1][i], {1, i}});
        d[1][i] = c[1][i];
        st.insert({c[n][i], {n, i}});
        d[n][i] = c[n][i];
    }
    while(!st.empty()){
        pair <ll, pair <int, int> > curr = *st.begin();
        st.erase(curr);
        int x = curr.s.f, y = curr.s.s;
        for(int i = 0; i < 4; i ++){
            int xx = x + dx[i], yy = y + dy[i];
            if(x <= 0 || x > n || y <= 0 || y > m){
                continue;
            }
            if(d[xx][yy] > d[x][y] + c[xx][yy]){
                st.erase({d[xx][yy], {xx, yy}});
                d[xx][yy] = d[x][y] + c[xx][yy];
                st.insert({d[xx][yy], {xx, yy}});
            }
        }
    }
    for(int x = 1; x <= n; x ++){
        for(int y = 1; y <= m; y ++){
            int dir = -1;
            ll cost = INFLL;
            for(int i = 0; i < 4; i ++){
                int xx = x + dx[i], yy = y + dy[i];
                ll curr_cost;
                if(xx == 0 || xx == n + 1 || yy == 0 || yy == m + 1){
                    curr_cost = 0;
                }
                else{
                    curr_cost = d[xx][yy];
                }
                if(curr_cost < cost){
                    cost = curr_cost;
                    dir = i;
                }
            }
            int xx = x + dx[dir], yy = y + dy[dir];
            if(xx == 0 || xx == n + 1 || yy == 0 || yy == m + 1){
                pr[x][y][0] = {0, 0};
            }
            else{
                pr[x][y][0] = {xx, yy};
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            g[pr[i][j][0].f][pr[i][j][0].s].pb({i, j});
        }
    }
    dfs(0, 0);
    int t = 1e5;
    cin >> t;
    while(t --){
        int x, y, k, xx, yy;
        pair <int, int> prr;
        cin >> x >> y >> k;
        xx = x; yy = y;
        for(int power = 20; power >= 0; power --){
            prr = pr[xx][yy][power];
            if(k > (1 << power)){
                k -= (1 << power);
                xx = prr.f;
                yy = prr.s;
            }
        }
        if(k){
            prr = pr[xx][yy][0];
            xx = prr.f;
            yy = prr.s;
        }
        if(!xx){
            xx = yy = -1;
        }
        cout << d[x][y] << ' ' << xx << ' ' << yy << '\n';
    }
    return 0;
}