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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#include <cstdio>
#include <unordered_map>
#include <string>
#include <vector>
#include <cassert>

#define LCM (8 * 7 * 5 * 3)
#define BML (LCM / 64 + 1)
#define MAXN 16000

typedef long long ll;
using std::string;

typedef struct bitmask {
  ll mask[BML]; 

  void clean() { for (int i = 0; i < BML; i++) mask[i] = 0LL; }
  void fill() { for (int i = 0; i < BML; i++) mask[i] = -1LL; }
  void set_at(int pos) {
    int base = pos / 64;
    int off = pos & 63;
    mask[base] |= (1LL << off);
  }

  bool get(int pos) {
    int base = pos / 64;
    int off = pos & 63;
    return mask[base] & (1LL << off);
  }

  string debug(int L) {
    string res = "";
    for (int i = 0; i < L; ++i) {
      res += (get(i) ? '1' : '0');
    }
    return res;
  }

  void do_or(const bitmask &b) {
    for (int i = 0; i < BML; ++i) mask[i] |= b.mask[i];
  }

  void do_and(const bitmask &b) {
    for (int i = 0; i < BML; ++i) mask[i] &= b.mask[i];   
  }

  void do_not() {
    for (int i = 0; i < BML; ++i) mask[i] = ~mask[i];
  }
} bitmask; 



std::unordered_map<string, bitmask> string_to_bitmask;

void fill_string_to_bitmask() {
  for (int l = 2; l < 9; ++l) {
    for (int code = 0; code < (1 << l); ++code) {
      std::string s = "";
      s.resize(l, '0');
      bitmask b;
      b.clean();
      for (int p = 0; p < l; ++p) {
        if (code & (1 << p)) {
          s[p] = '1';
          b.set_at(p);   
        }
      }
      for (int p = l; p < LCM; ++p) {
        if (b.get(p - l)) b.set_at(p);
      }
      string_to_bitmask[s] = b;   
    } // for (int code) 
  } // for(int l)
}    

std::vector<std::vector<bitmask>> intersections;   
int N, M, Q;
char tempstring[20];

bitmask vertical_masks[MAXN];  // Length M, 1 if I can cross the vertical street from i to i+1 
bitmask horizontal_masks[MAXN];  // Length N, 1 if I can cross the horizontal street from i to i+1.   

// vertical_forward_times[time_offset][jump_size][m] = X means it takes X time to get from plaza 
// (2 ** jump_size  * m to 2**jump_size * (m + 1), if we start at time time_offset. 
std::vector<int> vertical_forward_times[LCM][16]; 
// vertical_backward_times measure the time to get from 2 ** jumpsize * (m+1) to 2 ** jumpsize * m
std::vector<int> vertical_backward_times[LCM][16];
// horizontal_forward_times do the same from n to n+1
std::vector<int> horizontal_forward_times[LCM][16];
std::vector<int> horizontal_backward_times[LCM][16];

int calculate(int time, int from, int to, std::vector<int> forward[LCM][16], std::vector<int> backward[LCM][16]) {
  int cost = 0;
  if (from <= to) {
    while (from < to) {
      // Get the jump length.
      int jumplen = 0;
      while (from % (1 << (jumplen + 1)) == 0 && from + (1 << (jumplen + 1)) <= to) {
        jumplen += 1;
      }
      // Move by jumplen.
      int movecost = forward[time][jumplen][from / (1 << jumplen)];
      from += (1 << jumplen);
      cost += movecost;
      time = (time + movecost) % LCM;
    }
    return cost;
  } 
  // The reverse, let's get this right.
  while (from > to) {
    int jumplen = 0;
    while (from % (1 << (jumplen + 1)) == 0 && from - (1 << (jumplen + 1)) >= to) {
      jumplen += 1;
    }
    int movecost = backward[time][jumplen][(from / (1 << jumplen)) - 1];
    from -= (1 << jumplen);
    cost += movecost;
    time = (time + movecost) % LCM;
  }
  return cost;
}

int main() {
  // Fill in the string to bitmask converstion.
  fill_string_to_bitmask();

  // Set up the bitmasks on every intersection.
  scanf("%d %d %d\n", &N, &M, &Q);
  intersections.resize(N);
  for (int n = 0; n < N; ++n) {
    intersections[n].resize(M);
    for (int m = 0; m < M; ++m) {
      scanf("%s", tempstring);
      intersections[n][m] = string_to_bitmask[string(tempstring)]; 
    } 
  }

  // Calculate vertical masks - is there a crossing between vertical X and X+1.
  // There is no crossing if all the lights are on 0. Otherwise, there is. So, we OR the bitmasks. 
  for (int m = 0; m < M; ++m) {
    vertical_masks[m].clean();
    for (int n = 0; n < N; ++n) {
      vertical_masks[m].do_or(intersections[n][m]);
    }    
    // Now, it's a 1 if we can cross (if any light allowed a horizontal crossing).
  }
  for (int n = 0; n < N; ++n) {
    horizontal_masks[n].fill();
    for (int m = 0; m < M; ++m) {
      horizontal_masks[n].do_and(intersections[n][m]);
    }
    // Now, it's a 0 if we can cross (if any light allowed a vertical crossing). Let's reverse it.
    horizontal_masks[n].do_not();
  }

  // Let's calculate times. First, resize the vectors.
  for (int time_offset = 0; time_offset < LCM; ++time_offset) {
    for (int jump_size = 0; jump_size < 16; ++jump_size) {
      vertical_forward_times[time_offset][jump_size].resize(M / (1 << jump_size));
      vertical_backward_times[time_offset][jump_size].resize(M / (1 << jump_size));
      horizontal_forward_times[time_offset][jump_size].resize(N / (1 << jump_size));
      horizontal_backward_times[time_offset][jump_size].resize(N / (1 << jump_size));
    }
  }
  // Begin with time offset 0.
  // Now, I want the nearest zero, moving across time offsets forwards in time.
  // The last one, let's just do by hand.
  for (int m = 0; m < M; ++m) {
    int diff = 0;
    while (!vertical_masks[m].get((LCM + diff - 1) % LCM)) diff++;
    // Note that at jump size zero, the forward and backward times are equal - we just need to cross one crossing.
    vertical_forward_times[LCM-1][0][m] = vertical_backward_times[LCM-1][0][m] = diff;
    // The rest, we do with the standard DP.
    for (int time_offset = LCM - 2; time_offset >= 0; time_offset--) {
      vertical_forward_times[time_offset][0][m] = vertical_backward_times[time_offset][0][m] = 
        (vertical_masks[m].get(time_offset) ? 0 : vertical_forward_times[time_offset + 1][0][m] + 1); 
    } 
  }
  // Similarly for horizontals.
  for (int n = 0; n < N; ++n) {
    int diff = 0;
    while (!horizontal_masks[n].get((LCM + diff - 1) % LCM)) diff++;
    horizontal_forward_times[LCM-1][0][n] = horizontal_backward_times[LCM-1][0][n] = diff;
    for (int time_offset = LCM - 2; time_offset >= 0; time_offset--) {
      horizontal_forward_times[time_offset][0][n] = horizontal_backward_times[time_offset][0][n] =
        (horizontal_masks[n].get(time_offset) ? 0 : horizontal_forward_times[time_offset + 1][0][n] + 1);
    } 
  } 

  // Now, do the jumps. They are a simple aggregation.
  for (int jump_size = 1; jump_size < 16; ++jump_size) {
    for (int m = 0; (m + 1) * (1 << jump_size) < M + 1; ++m) {
      for (int time_offset = 0; time_offset < LCM; ++time_offset) {
        int first_jump = vertical_forward_times[time_offset][jump_size - 1][2 * m];
        int second_time = (time_offset + first_jump) % LCM;
        vertical_forward_times[time_offset][jump_size][m] = 
          first_jump + vertical_forward_times[second_time][jump_size - 1][2 * m + 1]; 

        first_jump = vertical_backward_times[time_offset][jump_size - 1][2 * m + 1];
        second_time = (time_offset + first_jump) % LCM;
        vertical_backward_times[time_offset][jump_size][m] = 
          first_jump + vertical_backward_times[second_time][jump_size - 1][2 * m];
      }
    }   

    for (int n = 0; (n + 1) * (1 << jump_size) < N + 1; ++n) {
      for (int time_offset = 0; time_offset < LCM; ++time_offset) {
        int first_jump = horizontal_forward_times[time_offset][jump_size - 1][2 * n];
        int second_time = (time_offset + first_jump) % LCM;
        horizontal_forward_times[time_offset][jump_size][n] =
          first_jump + horizontal_forward_times[second_time][jump_size - 1][2 * n + 1];
      
        first_jump = horizontal_backward_times[time_offset][jump_size - 1][2 * n + 1];
        second_time = (time_offset + first_jump) % LCM;
        horizontal_backward_times[time_offset][jump_size][n] =
          first_jump + horizontal_backward_times[second_time][jump_size - 1][2 * n];
      }
    }
  }

  // Aaaah, this was tiring. OK, let's do the queries.
  for (int q = 0; q < Q; ++q) {
    int starttime, nstart, mstart, nend, mend;
    scanf("%d %d %d %d %d", &starttime, &nstart, &mstart, &nend, &mend);
    // Time to cross the horizontal streets.
    int htime = calculate(starttime % LCM, nstart, nend, horizontal_forward_times, horizontal_backward_times);
    int vtime = calculate(starttime % LCM, mstart, mend, vertical_forward_times, vertical_backward_times);
    assert(htime == 0 || vtime == 0);
    printf("%d\n", starttime + htime + vtime);   
  }
  return 0;
}