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
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
#include <iostream>
#define CYCLE 840
using namespace std;
int n, m, q;

vector<string> s[15002];
set<int> blocks[842];
bool h[842], v[842];
int main () {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            string temp;
            cin >> temp;
            s[i].push_back(temp);
        }
    }

    for (int i = 1; i <= n; i++) {
        set<int> poss;
        set< pair<int, int> > typ;
        for (int j = 0; j < CYCLE ; j++) {
            poss.insert(j);
        }
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < s[i][j].length(); k++) {

                if (s[i][j][k] == '0') {
                    if (typ.find({k, s[i][j].length()}) == typ.end()) {
                        typ.insert({k, s[i][j].length()});
                        for (int l = k; l < CYCLE ; l += s[i][j].length()) {
                            poss.erase(l);
                        }
                    }
                }
            }
            if (poss.empty())
                break; 
        }
        if (!poss.empty()) {
            for (auto elem : poss) {
                h[elem] = true;
                blocks[elem].insert(i);
            }
        }
    }

    for (int i = 0; i < m; i++) {
        set<int> poss;
        set< pair<int, int> > typ;
        for (int j = 0; j < CYCLE ; j++) {
            poss.insert(j);
        }
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < s[j][i].length(); k++) {
                if (s[j][i][k] == '1') {
                    if (typ.find({k, s[j][i].length()}) == typ.end()) {
                        typ.insert({k, s[j][i].length()});
                        for (int l = k; l < CYCLE ; l += s[j][i].length()) {
                            poss.erase(l);
                        }
                    }
                }
            }
            if (poss.empty())
                break; 
        }
        if (!poss.empty()) {
            for (auto elem : poss) {
                v[elem] = true;
                blocks[elem].insert(i + 1);
            }
        }
    }
    // DEBUG
    // for (int i = 0; i <= 17; i++) {
    //     cout << "t: " << i << endl;
    //     if (h[i]) {
    //         cout << 'H' << endl;
    //     } else if (v[i]) {
    //         cout << 'V' << endl;
    //     }
    //     for (auto elem : blocks[i]) {
    //         cout << elem << " ";
    //     }
    //     cout << "_________" << endl;
    // }

    for (int i = 0; i < CYCLE ; i++) {
        if ((!h[i]) && (!v[i])) {
            continue;
        }
        blocks[i].insert(0);
        blocks[i].insert(16000);
    }
    while (q--) {
        int tim, x1, y1, x2, y2;
        cin >> tim >> x1 >> y1 >> x2 >> y2;
        int tim_mod  = tim % CYCLE;
        if ((!h[tim_mod]) && (!v[tim_mod])) {
            cout << tim << endl;
            continue;
        }
        if (v[tim_mod]) {
            x1 = y1;
            x2 = y2;
        }
        if (x1 == x2) {
            cout << tim << endl;
            continue;            
        }
        bool type_comp = h[tim_mod];
        int counter = tim;
        int pos = x1;
        while (1) {
            if ((type_comp && (!h[tim_mod])) || ((!type_comp) && (!v[tim_mod]))) {
                break;
            }
            if (x2 > pos) {
                int rang = *blocks[tim_mod].upper_bound(pos);
                if (rang > x2) {
                    break;
                }
                pos = rang;
            } else {
                auto iter = blocks[tim_mod].upper_bound(pos);
                int rang = *(--iter);
                // cout << "RANG " << rang << endl;
                if (rang <= x2) {
                    break;
                }
                pos = rang;
            }

            counter++;
            tim_mod = counter % CYCLE;
        }
        cout << counter << endl;
    }
    return 0;
}