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
#include <bits/stdc++.h> //Michał Kuśmirek
using namespace std;     //XIII LO Szczecin

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)

using ll = long long;
using pii = pair<int, int>;

template<class T> int size(T && a) {
	return (int)(a.size());
}
ostream& operator << (ostream &os, string str) {
    for(char c : str) os << c;
    return os;
}
template <class A, class B> ostream& operator << (ostream &os, const pair<A, B> &p) {
	return os << '(' << p.first << "," << p.second << ')';
}
template <class T> auto operator << (ostream &os, T &&x) -> decltype(x.begin(), os) {
	os << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		os << *it << (it == prev(x.end()) ? "" : " ");
	return os << '}';
}
template <class T> ostream& operator << (ostream &os, vector<vector<T>> vec) {
    for(auto x : vec)
    	os << "\n  " << x;
    return os;
}
void dump() {}
template <class T, class... Args> void dump(T &&x, Args... args) {
    cerr << x << "; ";
    dump(args...);
}
#ifdef DEBUG
# define debug(x...) cerr << "[" #x "]: ", dump(x), cerr << '\n'
#else 
# define debug(...) 0
#endif

//--------------------------------------------------

#ifdef DEBUG
	const int BITS = 12;
#else
	const int BITS = 840;
#endif

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

	vector<vector<bitset<BITS>>> s(n, vector<bitset<BITS>>(m));
	REP(i, n) REP(j, m) {
		string str; cin >> str;
		REP(k, BITS)
			s[i][j][k] = (str[k % size(str)] - '0');
	}

	vector<int> orientation(BITS); //0 - none, 1 - horizontal, 2 - vertical
	vector<vector<int>> rows(n);
	REP(i, n) {
		bitset<BITS> ret = s[i][0];
		REP(j, m)
			ret &= s[i][j];

		debug(ret);

		REP(k, BITS)
			if(!ret[k])
				rows[i].emplace_back(k);
			else
				orientation[k] = 1;
	}

	vector<vector<int>> cols(m);
	REP(j, m) {
		bitset<BITS> ret = s[0][j];
		REP(i, n)
			ret |= s[i][j];

		REP(k, BITS)
			if(ret[k])
				cols[j].emplace_back(k);
			else
				orientation[k] = 2;
	}

	debug(rows);
	debug(cols);
	debug(orientation);

	while(q--) {
		int t, a, b, c, d;
		cin >> t >> a >> b >> c >> d;

		int current_time = t;
		if(orientation[t % BITS] == 1) {
			int diff = (a <= c ? 1 : -1);
			if(a > c) --a, --c;
			for(int i = a; i != c; i += diff) {
				auto it = lower_bound(rows[i].begin(), rows[i].end(), current_time % BITS);
				if(it == rows[i].end())
					it = rows[i].begin();
				current_time += (BITS + *it - current_time % BITS) % BITS;
			}
		} else {
			int diff = (b <= d ? 1 : -1);
			if(b > d) --b, --d;
			for(int i = b; i != d; i += diff) {
				auto it = lower_bound(cols[i].begin(), cols[i].end(), current_time % BITS);
				if(it == cols[i].end())
					it = cols[i].begin();
				current_time += (BITS + *it - current_time % BITS) % BITS;
			}
		}

		cout << current_time << '\n';
	}


}