1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;

#ifdef D
#define DEBUG(x)        \
    do {                \
        x               \
        cout.flush();   \
    } while (0)
#else
#define DEBUG(x)
#endif

const int NMAX = 1e6 + 7;

int n, m, q, tt, a, b, x, y, io;
vector<vector<int>> t;
vector<vector<string>> s;
vector<vector<int>> vis;
bool ok;

void dfs(int vy, int vx) {
    vis[vy][vx] = io;
    if (vx == x && vy == y) {
        ok = 1;
        return;
    }
    // w prawo
    if (vx < m) {
        if (vis[vy][vx + 1] < io) {
            if (vy < n && s[vy][vx][tt % s[vy][vx].size()] == '1') { // dolne
                dfs(vy, vx + 1);
            } else if (vy > 0 && s[vy - 1][vx][tt % s[vy - 1][vx].size()] == '1') { // gorne
                dfs(vy, vx + 1);
            }
        }
    }
    // w lewo
    if (vx > 0) {
        if (vis[vy][vx - 1] < io) {
            if (vy < n && s[vy][vx - 1][tt % s[vy][vx - 1].size()] == '1') { // dolne
                dfs(vy, vx - 1);
            } else if (vy > 0 && s[vy - 1][vx - 1][tt % s[vy - 1][vx - 1].size()] == '1') { // gorne
                dfs(vy, vx - 1);
            }
        }
    }
    // w dol
    if (vy < n) {
        if (vis[vy + 1][vx] < io) {
            if (vx < m && s[vy][vx][tt % s[vy][vx].size()] == '0') { // prawe
                dfs(vy + 1, vx);
            } else if (vx > 0 && s[vy][vx - 1][tt % s[vy][vx - 1].size()] == '0') { // lewe
                dfs(vy + 1, vx);
            }
        }
    }
    // w gore
    if (vy > 0) {
        if (vis[vy - 1][vx] < io) {
            if (vx < m && s[vy - 1][vx][tt % s[vy - 1][vx].size()] == '0') { // prawe
                dfs(vy - 1, vx);
            } else if (vx > 0 && s[vy - 1][vx - 1][tt % s[vy - 1][vx - 1].size()] == '0') { // lewe
                dfs(vy - 1, vx);
            }
        }
    }
}

void solve() {
    ok = 0;
    io++;
    dfs(b, a);
    while (!ok) {
        io++;
        tt++;
        for (int i = 0; i <= n && !ok; ++i) {
            for (int j = 0; j <= m && !ok; ++j) {
                if (vis[i][j] == io - 1) {
                    dfs(i, j);
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    t.resize(n);
    s.resize(n);
    vis.resize(n + 1);
    vis[n].resize(m + 1);
    for (int i = 0; i < n; ++i) {
        t[i].resize(m);
        s[i].resize(m);
        vis[i].resize(m + 1);
        for (int j = 0; j < m; ++j) {
            cin >> s[i][j];
        }
    }
    for (int i = 0; i < q; ++i) {
        cin >> tt >> b >> a >> y >> x;
        solve();
        cout << tt << "\n";
    }
    return 0;
}