#include <algorithm>
// #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 15000;
const int MAXM = 15000;
const int MAXT = /*4*3;//*/8*7*5*3;
const int MAXCYCLES = 8;
const int MAXB = 8;
const int MAXWORD = 8;

const int INF = 1000000000;
using para = pair<int,int>;
using bajt = unsigned;
#define FOR(i, n) for(int i = 0, __n = (n); i < __n; i++)

int n, m, q;
bajt * T[MAXN];
char * Tc[MAXN];

char buffer[MAXWORD+1];

bool row[MAXT][MAXN];
bool col[MAXT][MAXN];

bajt MASK[MAXB+1] = {
  0,
  (1<<1)-1, (1<<2)-1, (1<<3)-1, (1<<4)-1, (1<<5)-1, (1<<6)-1, (1<<7)-1, 255
};

vector<para>* rowR[MAXT];//[MAXN+1];
vector<para>* colR[MAXT];//[MAXM+1];

const int JUMPC = /*3;//*/6;
const int DEFJUMP = 4;
int JUMPS[JUMPC] = /*{2,2,3};//*/
// {7, 5, 3, 2, 2, 2};
// {2, 2, 2, 3, 5, 7};
{4, 7, 5, 6, 4, 3, };
int JUMP[MAXCYCLES];

int main() {
  // ios_base::sync_with_stdio(0);

  // cin >> n >> m >> q;
  scanf("%d%d%d", &n, &m, &q);
  FOR(t, MAXT) {
    rowR[t] = new vector<para>[n+1];
    colR[t] = new vector<para>[m+1];
  }

  // wczytaj dane:
  FOR(i, n) {
    T[i] = new bajt[m];
    Tc[i] = new char[m];
    FOR(j, m) {
      // cin >> buffer;
      scanf("%s", buffer);
      int len = strlen(buffer);

      Tc[i][j] = len;
      bajt b = 0;
      FOR(k, len) {
        if(buffer[k] == '1') b |= (1<<k);
      }
      T[i][j] = b;
    }
  }

// cerr <<"PREDUPA1" << endl;
  // policz spójne wiersze
  FOR(i, n) {
    bajt flags[MAXB + 1];
    FOR(j, MAXB+1) flags[j] = 0;
    FOR(j, m) {
      int pos = Tc[i][j];
      int mask = T[i][j];
      mask = ~mask; // for rows, skip for cols
      mask &= MASK[pos]; 
      flags[pos] |= mask;
    }

    FOR(t, MAXT) {
      bool connected = false;
      for(int k = 2; !connected && k<=MAXB; k++) {
        int pos = t%k;
        connected = (connected || (flags[k] & (1<<pos)));
      }
      row[t][i] = connected;
    }
  }

// cerr <<"PREDUPA2" << endl;
  // policz spójne kolumny
  FOR(i, m) {
    bajt flags[MAXB + 1];
    FOR(j, MAXB+1) flags[j] = 0;
    FOR(j, n) {
      int pos = Tc[j][i];
      int mask = T[j][i];
      flags[pos] |= mask;
    }

    FOR(t, MAXT) {
      bool connected = false;
      for(int k = 2; !connected && k<=MAXB; k++) {
        int pos = t%k;
        connected = (connected || (flags[k] & (1<<pos)));
      }
      col[t][i] = connected;
    }
  }

// cerr <<"PREDUPA" << endl;
  // policz spójne zakresy
  FOR(t, MAXT) {
    int from = 0;
    for(int i = 0; i<=n; i++) {
      if(i == n || !row[t][i]) {
        for(int k = from; k<=i; k++) {
          rowR[t][k].push_back(para(from,i));
        }
        from = i+1;
      }
    }
    from = 0;
    for(int i = 0; i<=m; i++) {
      if(i == m || !col[t][i]) {
        for(int k = from; k<=i; k++) {
          colR[t][k].push_back(para(from,i));
        }
        from = i+1;
      }
    }
  }



// cerr << "DUPA" << endl;
  int jump = 1;
  for(int k = 0; k < MAXCYCLES; k++) {
    int rep;
    if(k >= JUMPC) rep = DEFJUMP;
    else rep = JUMPS[k];
    JUMP[k] = jump;
    // cerr << "k=" << k << ": " << jump << endl;

    for(int t = 0; t < MAXT; t+=jump*rep) {
      for(int i = 0; i<=n; i++) {
        int a = i, b=i;
        int t1 = t;
        FOR(r, rep) {
          a = rowR[t1][a][k].first;
          b = rowR[t1][b][k].second;
          t1 = (t1+jump) % MAXT;
        }
        rowR[t][i].push_back(para(a,b));
      }

      for(int i = 0; i<=m; i++) {
        int a = i, b=i;
        int t1 = t;
        FOR(r, rep) {
          a = colR[t1][a][k].first;
          b = colR[t1][b][k].second;
          t1 = (t1+jump) % MAXT;
        }
        colR[t][i].push_back(para(a,b));
      }
    }
    jump *= rep;
    // cerr << jump <<endl;;
  }

  // FOR(t, MAXT) {
  //   cerr<< "t=" << t << "\t";
  //   FOR(i, n) {
  //     cerr << (row[t][i] ? '1':'0');
  //   }
  //   cerr << "\t";
  //   FOR(i, m) {
  //     cerr << (col[t][i] ? '1':'0');
  //   }
  //   cerr << "\t";
  //   FOR(k, min(6ul, rowR[t][0].size())){
  //     FOR(i, n+1) {
  //       cerr << "{" << rowR[t][i][k].first << "," << rowR[t][i][k].second << "}";
  //     }
  //     cerr <<" ";
  //   }
  //   cerr << endl<<"\t\t\t";
  //   FOR(k, min(6ul, rowR[t][0].size())){
  //     FOR(i, m+1) {
  //       cerr << "{" << colR[t][i][k].first << "," << colR[t][i][k].second << "}";
  //     }
  //     cerr <<" ";
  //   }
  //   cerr << endl;
  // }

// cerr << "DUPA2" << endl;


  long long iters = 0;
  FOR(que, q) {
    int t, x1, y1, x2, y2;
    // cin >> t >> x1 >> y1 >> x2 >> y2;
    scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2);

    // cerr << "> " << t << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    int xa = rowR[t%MAXT][x1][0].first, xb = rowR[t%MAXT][x1][0].second, ya = colR[t%MAXT][y1][0].first, yb = colR[t%MAXT][y1][0].second;

    if(xa<=x2 && xb >= x2 && ya <= y2 && yb >= y2) {
      printf("%d\n", t);
      // cout << t << endl;
      continue;
    }

    if(x2 < xa) {
      unsigned long maxj = MAXCYCLES;
      while (maxj > 0 && x2 < xa) {
        int t1 = t%MAXT;
        int realmax = min(rowR[t1][xa].size(), maxj);

        for (int k = realmax-1; k>=0; k--) {
          int xa1 = rowR[t1][xa][k].first;
          iters ++;
          if(xa1<=x2) {
            maxj = k;
          } else {
            xa = xa1;
            t += JUMP[k];
            break;
          }
        }
      }
    } else if(x2 > xb) {
      unsigned long maxj = MAXCYCLES;
      while (maxj > 0 && x2 > xb) {
        int t1 = t%MAXT;
        int realmax = min(rowR[t1][xb].size(), maxj);

        for (int k = realmax-1; k>=0; k--) {
          int xb1 = rowR[t1][xb][k].second;
          iters ++;
          if(xb1>=x2) {
            maxj = k;
          } else {
            xb = xb1;
            t += JUMP[k];
            break;
          }
        }
      }
    } else if(y2 < ya) {
      unsigned long maxj = MAXCYCLES;
      while (maxj > 0 && y2 < ya) {
        int t1 = t%MAXT;
        int realmax = min(colR[t1][ya].size(), maxj);

        for (int k = realmax-1; k>=0; k--) {
          int ya1 = colR[t1][ya][k].first;
          iters ++;
          if(ya1<=y2) {
            maxj = k;
          } else {
            ya = ya1;
            t += JUMP[k];
            break;
          }
        }
      }
    } else if(y2 > yb) {
      unsigned long maxj = MAXCYCLES;
      while (maxj > 0 && y2 > yb) {
        int t1 = t%MAXT;
        int realmax = min(colR[t1][yb].size(), maxj);

        for (int k = realmax-1; k>=0; k--) {
          int yb1 = colR[t1][yb][k].second;
          iters ++;
          if(yb1>=y2) {
            maxj = k;
          } else {
            yb = yb1;
            t += JUMP[k];
            break;
          }
        }
      }
    } /*else {

      unsigned long maxj = MAXCYCLES;
      while(maxj > 0 && !(xa<=x2 && xb >= x2 && ya <= y2 && yb >= y2)) {
        // cerr << t << " " << xa << " " << xb << " " << ya << " " << yb << endl;
        int t1 = t%MAXT;
        int realmax = min(rowR[t1][xa].size(), maxj);
        
          iters ++;

        for (int k = realmax-1; k>=0; k--) {
          int xa1 = rowR[t1][xa][k].first;
          int xb1 = rowR[t1][xb][k].second;
          int ya1 = colR[t1][ya][k].first;
          int yb1 = colR[t1][yb][k].second;
          iters ++;
          if(xa1<=x2 && xb1 >= x2 && ya1 <= y2 && yb1 >= y2) {
            maxj = k;
          } else {
            xa = xa1;
            xb = xb1;
            ya = ya1;
            yb = yb1;
            t += JUMP[k];
            break;
          }
        }
      }
    }*/
    printf("%d\n", t);
    // cout << t << endl; 
    //" " << iters << endl;
    // cout << t << " " << iters << endl;
  }
  // cerr << "ITERS " << iters << endl;
}