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
#include <bits/stdc++.h>
using namespace std;
const int MX=1000100,MK=18,MS=15105;
int n,m,q,num,nm,i,j,x,y,idx,t,ot,st,nxt,lcm_,ca[MS],cb[MS],len[MX],pos[MX];
short le[MK][842][MS],ri[MK][842][MS];
char s[MX][9];
bool was[9];
int gcd(int a, int b) { return b?gcd(b,a%b):a; }
int main() {
  scanf("%d%d%d",&n,&m,&q);
  for (i=0; i<n; i++) for (j=0; j<m; j++, num++) {
    scanf("%s",s[num]);
    len[num]=strlen(s[num]);
    for (x=0; x<len[num]; x++) s[num][x]-='0';
    was[len[num]]=true;
    pos[num]=0;
  }
  lcm_=1;
  for (i=2; i<=8; i++) lcm_=(lcm_/gcd(lcm_,i))*i;
  nm=n+1+m;
  for (t=0; t<lcm_; t++) {
    for (i=0; i<n; i++) ca[i]=0;
    for (i=0; i<m; i++) cb[i]=0;
    for (i=idx=0; i<n; i++) {
      for (j=0; j<m; j++, idx++) {
        ca[i]+=s[idx][pos[idx]];
        cb[j]+=s[idx][pos[idx]];
        if (++pos[idx]==len[idx]) pos[idx]=0;
      }
      le[0][t][i+1]=(ca[i]==m)?(i+1):le[0][t][i];
    }
    ri[0][t][n]=n;
    for (i=n-1; i>=0; i--) ri[0][t][i]=(ca[i]==m)?i:ri[0][t][i+1];
    le[0][t][n+1]=n+1;
    for (j=1; j<=m; j++) le[0][t][n+1+j]=(cb[j-1]==0)?(n+1+j):le[0][t][n+j];
    ri[0][t][nm]=nm;
    for (j=m-1; j>=0; j--) ri[0][t][n+1+j]=(cb[j]==0)?(n+1+j):ri[0][t][n+2+j];
    /*if (t==0) {
        for (i=0; i<n; i++) printf("%d ",ca[i]); puts("ca");
        for (i=0; i<m; i++) printf("%d ",cb[i]); puts("cb");
      for (i=0; i<=n; i++) printf("%d ",le[0][t][i]); puts("le-i");
      for (i=0; i<=n; i++) printf("%d ",ri[0][t][i]); puts("ri-i");
      for (i=0; i<=m; i++) printf("%d ",le[0][t][n+1+i]); puts("le-j");
      for (i=0; i<=m; i++) printf("%d ",ri[0][t][n+1+i]); puts("ri-j");
    }*/
  }
  for (st=1; st<MK; st++) {
    nxt=(1<<(st-1))%lcm_;  
    for (t=0; t<lcm_; t++) {
      for (i=0; i<=nm; i++) {
        le[st][t][i]=le[st-1][nxt][le[st-1][t][i]];
        ri[st][t][i]=ri[st-1][nxt][ri[st-1][t][i]];
      }
      if (++nxt==lcm_) nxt=0;
    }
  }
  while (q--) {
    scanf("%d%d%d%d%d",&t,&i,&j,&x,&y);
    j+=n+1;
    y+=n+1;
    ot=t%lcm_;
    if (x>=le[0][ot][i] && x<=ri[0][ot][i]) {
      if (y>=le[0][ot][j] && y<=ri[0][ot][j]) { printf("%d\n",t); continue; }
      if (y<j) for (st=MK-1; st>=0; st--) while (le[st][ot][j]>y) {
        j=le[st][ot][j];
        t+=(1<<st);
        ot=t%lcm_;
      } else if (y>j) for (st=MK-1; st>=0; st--) while (ri[st][ot][j]<y) {
        j=ri[st][ot][j];
        t+=(1<<st);
        ot=t%lcm_;
      }
    } else {
      assert(y>=le[0][ot][j] && y<=ri[0][ot][j]);
      assert(x>=le[MK-1][ot][i] && x<=ri[MK-1][ot][i]);
      if (x<i) for (st=MK-1; st>=0; st--) while (le[st][ot][i]>x) {
        i=le[st][ot][i];
        t+=(1<<st);
        ot=t%lcm_;
      } else if (x>i) for (st=MK-1; st>=0; st--) while (ri[st][ot][i]<x) {
        i=ri[st][ot][i];
        t+=(1<<st);
        ot=t%lcm_;
      }
    }
    printf("%d\n",t);
  }
  return 0;
}