#include <bits/stdc++.h>
using namespace std;
//using namespace std::chrono;

char get_state(string& s, int t) {
   return s[t % s.size()];
}

vector<int> get_indices_of_true(vector<bool>& v) {
   vector<int> res;
   for (int i = 0; i < v.size(); i++) {
      if (v[i]) {
         res.push_back(i);
      }
   }
   return res;
}

struct CityBlocks {
   bool on_i;
   vector<int> indices;
};

CityBlocks analyze_time(int t, vector<vector<string>>& s) {
   // search rows full of '1' or columns full of '0'
   vector<bool> blocked_i(s.size(), true);
   vector<bool> blocked_j(s[0].size(), true);

   for (int i = 0; i < s.size(); i++) {
      for (int j = 0; j < s[i].size(); j++) {
         if (blocked_i[i] || blocked_j[j]) {
            if (get_state(s[i][j], t) == '0') {
               blocked_i[i] = false;
            } else {
               blocked_j[j] = false;
            }
         }
      }
   }

   vector<int> i_idx = get_indices_of_true(blocked_i);
   if (i_idx.size() > 0) {
      return {true, i_idx};
   } else {
      return {false, get_indices_of_true(blocked_j)};
   }
}

struct Successors {
   vector<vector<int>> successor[2]; // 0=lo, 1=hi
};

Successors calc(CityBlocks& cur, CityBlocks& next) {
   Successors res;
   res.successor[0] = vector<vector<int>>(cur.indices.size());
   res.successor[1] = vector<vector<int>>(cur.indices.size());

   if (cur.on_i != next.on_i) {
      for (int i = 0; i < cur.indices.size(); i++) {
         res.successor[1][i].push_back(-1);
         res.successor[0][i].push_back(-1);
      }
      return res;
   }

   int idx_in_next = 0;
   for (int i = 0; i < cur.indices.size(); i++) {
      while (idx_in_next < next.indices.size() && next.indices[idx_in_next] < cur.indices[i]) {
         idx_in_next++;
      }
      int res1 = idx_in_next;
      if (res1 == next.indices.size()) {
         res1 = -1;
      }
      res.successor[1][i].push_back(res1);

      int res2 = idx_in_next;
      if (!(res2 < next.indices.size() && next.indices[res2] == cur.indices[i])) {
         res2--;
      }
      res.successor[0][i].push_back(res2);
   }

   return res;
}

int main() {
   //freopen("1.in", "r", stdin);
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   // auto start = high_resolution_clock::now();

   int n, m, q;
   cin >> n >> m >> q;
   vector<vector<string>> s(n, vector<string>(m));
   for (auto& si : s) {
      for (auto& sij : si) {
         cin >> sij;
      }
   }

   //cout << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << "loading" << endl;
   // modulo max 8 => at most 840 light patterns
   //
   // only whole roads with green lights can block passage
   // so we need to know if they are vert or horiz and which ones
   //
   // its never worth to go away from target, so for every blocked road we need to know
   // how long till it opens and which road blocks us then
   // (new blocker must have the same direction - if not we've reached destination)

   int max_time = 840;
   vector<CityBlocks> by_time(max_time);
   for (int t = 0; t < max_time; t++) {
      by_time[t] = analyze_time(t, s);
      // cout << t << " " << by_time[t].on_i << " " << by_time[t].indices.size() << '\n';
   }

   // cout << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << endl;
   // first lets find blocker in next timestamp
   vector<Successors> succs(max_time);
   for (int t = 0; t < max_time; t++) {
      succs[t] = calc(by_time[t], by_time[(t + 1) % max_time]);
   }

   //cout << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << endl;
   //cout << "succs levels" << endl;
   // possibly need something better for 1M queries :(
   // very pesimistic estmation o path length is ~15k * 8...
   // if thats correct we need structure of blockers: 1, 2, 4, 8... steps in future
   for (int level = 0; level < 12; level++) {
      for (int dir = 0; dir < 2; dir++) {
         for (int t = 0; t < max_time; t++) {
            int t2 = (t + (1 << level)) % max_time;
            for (int b = 0; b < succs[t].successor[dir].size(); b++) {
               auto& arr = succs[t].successor[dir][b];
               int next1 = arr[level];
               int next2 = -1;
               if (next1 != -1 && by_time[t].on_i == by_time[t2].on_i) {
                  next2 = succs[t2].successor[dir][next1][level];
               }
               arr.push_back(next2);
            }
         }
      }
   }

   //cout << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << endl;
   //cout << "clean -1 from end" << endl;
   for (int dir = 0; dir < 2; dir++) {
      for (int t = 0; t < max_time; t++) {
         for (int b = 0; b < succs[t].successor[dir].size(); b++) {
            auto& arr = succs[t].successor[dir][b];
            while (arr.size() > 1 && arr.back() == -1) {
               arr.pop_back();
            }
         }
      }
   }

   //cout << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << endl;
   //cout << "loop q" << endl;
   while (q--) {
      int tme, a, b, c, d;
      cin >> tme >> a >> b >> c >> d;
      CityBlocks& cb = by_time[tme % max_time];
      int tme0 = tme;
      int s = a;
      int t = c;
      if (!cb.on_i) {
         s = b;
         t = d;
      }

      int cur_blocker = -1;
      if (cb.indices.size() > 0) {
         if (s < t) {
            int dir = 1;
            // start with field "s", smallest line with s or more will block us
            auto it = lower_bound(cb.indices.begin(), cb.indices.end(), s);
            if (it != cb.indices.end()) {
               cur_blocker = distance(cb.indices.begin(), it);
            }

            while (cur_blocker != -1 && by_time[tme % max_time].indices[cur_blocker] < t) {
               auto& sucks = succs[tme % max_time].successor[dir][cur_blocker];
               int l = sucks.size() - 1;
               while (l > 0 && !(by_time[(tme + (1 << l)) % max_time].indices[sucks[l]] < t)) { //same condition as in while
                  l--;
               }
               // set l=0 for slow version
               cur_blocker = sucks[l];
               tme += (1 << l);
            }
         } else if (s > t) {
            int dir = 0;
            // largest line with value s-1 or less will block us
            auto it = upper_bound(cb.indices.begin(), cb.indices.end(), s - 1);
            cur_blocker = distance(cb.indices.begin(), it) - 1;

            while (cur_blocker != -1 && by_time[tme % max_time].indices[cur_blocker] >= t) {
               auto& sucks = succs[tme % max_time].successor[dir][cur_blocker];
               int l = sucks.size() - 1;
               while (l > 0 && !(by_time[(tme + (1 << l)) % max_time].indices[sucks[l]] >= t)) { //same condition as in while
                  l--;
               }
               //set l=0 for slow version
               cur_blocker = sucks[l];
               tme += (1 << l);
            }
         }
      }

      cout << tme << '\n';
   }

   //cout << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << endl;
}