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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <vector>
using namespace std;

const int C = 15000;

int main() {
    int n,m,Q;
    cin>>n>>m>>Q;
    vector<string> S[C];
    string s;
    for(int i=0; i<n; ++i)
    for(int j=0; j<m; ++j) {
        cin>>s;
        S[i].push_back(s);
    }
    int T = 840;
    vector< vector<bool> > L,P,G,D;
    vector<bool> V;
    for(int i=0; i<840; ++i) V.push_back(true);
    for(int i=0; i<C+1; ++i) {
        L.push_back(V);
        P.push_back(V);
        G.push_back(V);
        D.push_back(V);
    }
    
    for(int t=0; t<840; ++t) {
        for(int j=0; j<m+1; ++j) {
            bool czP = false, czL = false;
            for(int i=0; i<n; ++i) {
                
                int y;
                if(j<m) {
                    y = t % S[i][j].size();
                    if(S[i][j][y] == '1') czP = true;
                }
                if(j>0) {
                    y = t % S[i][j-1].size();
                    if(S[i][j-1][y] == '1') czL = true;
                }
            }
            P[j][t] = czP;
            L[j][t] = czL;
        }
        for(int i=0; i<n+1; ++i) {
            bool czG = false, czD = false;
            for(int j=0; j<m; ++j) {
                
                int y;
                if(i<n) {
                    y = t % S[i][j].size();
                    if(S[i][j][y] == '0') czD = true;
                }
                if(i>0) {
                    y = t % S[i-1][j].size();
                    if(S[i-1][j][y] == '0') czG = true;
                }
            }
            G[i][t] = czG;
            D[i][t] = czD;
        }
    }
    int h = 16;
    //cout<<true<<endl;
    //for(int i=0; i<n+1; ++i) cout<<i<<" G "<<G[i][h]<<" D "<<D[i][h]<<endl;
    //for(int i=0; i<m+1; ++i) cout<<i<<" P "<<P[i][h]<<" L "<<L[i][h]<<endl;
    
    for(int q=0; q<Q; ++q) {
        int t,a,b,c,d;
        int tt,odp = 0;
        cin>>tt>>a>>b>>c>>d;
        t = tt % T;
        if(a < c) {
            while(D[a][t] && a < c) a++;
            if(a == c) {
                if(b < d) {
                    while(P[b][t] && b < d) b++;
                    while(b < d) {
                        odp++;
                        t = (t+1) % T;
                        while(P[b][t] && b < d) b++;
                    }
                }
                else {
                    while(L[b][t] && b > d) b--;
                    while(b > d) {
                        odp++;
                        t = (t+1) % T;
                        while(L[b][t] && b > d) b--;
                    }
                }
            }
            else while(a < c) {
                odp++;
                t = (t+1) % T;
                while(D[a][t] && a < c) a++;
            }
        }
        else {
            while(G[a][t] && a > c) a--;
            if(a == c) {
                if(b < d) {
                    while(P[b][t] && b < d) b++;
                    while(b < d) {
                        odp++;
                        t = (t+1) % T;
                        while(P[b][t] && b < d) b++;
                    }
                }
                else {
                    while(L[b][t] && b > d) b--;
                    while(b > d) {
                        odp++;
                        t = (t+1) % T;
                        while(L[b][t] && b > d) b--;
                    }
                }
            }
            else while(a > c) {
                odp++;
                t = (t+1) % T;
                while(G[a][t] && a > c) a--;
            }
        }
        cout<<tt+odp<<endl;
    }
    
    
    return 0;
}