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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <iostream>
#include <limits>
#include <vector>
#include <string>
using namespace std;
typedef pair<short,short> pss;
const int timepoints = 8*7*5*3;
const int jumper_init_reserve = 10;

struct ColumnOrRow{
    bool forbidden[8][9]; //f[x][y] = true  <==>  dla tej kolumny reszta x modulo y jest zabroniona, czyli wtedy da się przejść
    bool is_forbidden(int tp) {
        for(int mod=2;mod<=8;mod++)
            if(forbidden[tp%mod][mod])
                return true;
        return false;
    }
    bool is_blocked(int tp) {
        return !is_forbidden(tp);
    }
    ColumnOrRow() {
        fill((bool*)forbidden, (bool*)forbidden+sizeof(forbidden), false);
    }
};

template<typename T>
void vector_init(T*& tab, int size){
    tab = new T[size];
}

struct Range{
    short from, to;
    
    pss* jumpers;
    bool in_range(int pos) {
        return pos>=from && pos<=to;
    }
};

struct Timepoint{
    bool row_mode;
    vector<Range> ranges;

    bool in_range_range(int pos, int ra, int rb) {
        if (ra==0 && rb==ranges.size()-1)
            return true;
        return ranges[ra].from<=pos && pos<=ranges[rb].to;
    }
    int get_range_id(int pos) {
        int ra = 0, rb = ranges.size()-1;
        while(ra<rb) {
            int rm = (ra+rb)/2;
            if(pos<=ranges[rm].to)
                rb = rm;
            else
                ra = rm+1;
        }
        return ra;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,q;
    cin >> n >> m >> q;

    //make column/row stats
    vector<ColumnOrRow>Columns(m),Rows(n);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            string seq;
            cin >> seq;
            int seq_len = seq.length();
            for(int k=0;k<seq_len;k++)
                if(seq[k]=='0') //przejście pionowe - blokada wiersza
                    Rows[i].forbidden[k][seq_len] = true;
                else
                    Columns[j].forbidden[k][seq_len] = true;
        }

    //prepare timepoints
    vector<Timepoint>TP(timepoints);
    for(int tp=0; tp<timepoints; tp++) {
        //find mode
        TP[tp].row_mode = true;
        for(int j=0;j<m;j++)
            if(Columns[j].is_blocked(tp)){
                TP[tp].row_mode = false;
                break;
            }
        
        //fill ranges
        short block_start = 0;
        vector<ColumnOrRow>&CoR = TP[tp].row_mode ? Rows : Columns;
        for(short i=0; i<(int)CoR.size(); i++)
            if (CoR[i].is_blocked(tp)) {
                TP[tp].ranges.push_back(Range{.from=block_start, .to=i});
                block_start = i+1;
            }
        TP[tp].ranges.push_back(Range{.from=block_start, .to=(short)CoR.size()});
    }

    //make initial jumpers
    for(int tp=0;tp<timepoints;tp++) {
        Timepoint &current_tp = TP[tp];
        Timepoint &future_tp = TP[(tp+1)%timepoints];

        //special edge case
        if (current_tp.row_mode != future_tp.row_mode) {
            for (Range &r : current_tp.ranges){
                vector_init(r.jumpers, jumper_init_reserve);
                r.jumpers[0] = pss{0, future_tp.ranges.size()-1};
            }
            continue;
        }

        //normal case
        int future_it_left = 0, future_it_right = 0;
        for (Range &r : current_tp.ranges) {
            while (future_tp.ranges[future_it_left].to < r.from)
                future_it_left++;
            while (future_it_right+1 < (int)future_tp.ranges.size() && r.to >= future_tp.ranges[future_it_right+1].from)
                future_it_right++;
            vector_init(r.jumpers, jumper_init_reserve);
            r.jumpers[0] = pss{future_it_left, future_it_right};
        }
    }

    //prepare for jumpers creation
    int current_jumpers = 1, current_jumper_size = 1;
    auto make_more_jumpers = [&](){
        for(int tp=0;tp<timepoints;tp++) {
            Timepoint &current_tp = TP[tp];
            Timepoint &target_tp1 = TP[(tp+current_jumper_size)%timepoints];
            Timepoint &target_tp2 = TP[(tp+2*current_jumper_size)%timepoints];
            Timepoint &target_tp3 = TP[(tp+3*current_jumper_size)%timepoints];

            for(Range& r : current_tp.ranges){
                short rl = r.jumpers[current_jumpers-1].first;
                short rr = r.jumpers[current_jumpers-1].second;

                rl = target_tp1.ranges[rl].jumpers[current_jumpers-1].first;
                rr = target_tp1.ranges[rr].jumpers[current_jumpers-1].second;

                rl = target_tp2.ranges[rl].jumpers[current_jumpers-1].first;
                rr = target_tp2.ranges[rr].jumpers[current_jumpers-1].second;

                rl = target_tp3.ranges[rl].jumpers[current_jumpers-1].first;
                rr = target_tp3.ranges[rr].jumpers[current_jumpers-1].second;

                r.jumpers[current_jumpers] = pss{rl, rr};
            }
        }
        current_jumpers++;
        current_jumper_size *= 4;
    };

    //process queries
    while(q--) {
        int t, a, b, c, d;
        cin >> t >> a >> b >> c >> d;
        int start_point = TP[t%timepoints].row_mode ? a : b;
        int stop_point = TP[t%timepoints].row_mode ? c : d;

        int init_range = TP[t%timepoints].get_range_id(start_point);
        int rl = init_range, rr = init_range;

        if (TP[t%timepoints].ranges[init_range].in_range(stop_point)) {
            cout << t << "\n";
            continue;
        }

        auto in_range_after_jump = [&](int jump_id, int jump_size) -> bool {
            return TP[(t+jump_size)%timepoints].in_range_range(stop_point, TP[t%timepoints].ranges[rl].jumpers[jump_id].first, TP[t%timepoints].ranges[rr].jumpers[jump_id].second);
        };

        auto jump_if_not_in_range_after_jump = [&](int jump_id, int jump_size, int &rl, int &rr, int &t){
            if(!in_range_after_jump(jump_id, jump_size)) {
                rl = TP[t%timepoints].ranges[rl].jumpers[jump_id].first;
                rr = TP[t%timepoints].ranges[rr].jumpers[jump_id].second;
                t += jump_size;
            }
        };

        while(!in_range_after_jump(current_jumpers-1, current_jumper_size)) 
            make_more_jumpers();
        
        for(int jump_id=current_jumpers-2,jump_size=current_jumper_size/4;jump_id>=0;jump_id--,jump_size/=4){
            jump_if_not_in_range_after_jump(jump_id, jump_size, rl, rr, t);
            jump_if_not_in_range_after_jump(jump_id, jump_size, rl, rr, t);
            jump_if_not_in_range_after_jump(jump_id, jump_size, rl, rr, t);
        }
        
        cout << t+1 << "\n";
    }

    return 0;
}