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
#include <bits/stdc++.h>
#define pb push_back
#define ss second
#define sz size()
#define ff first
#define tp top()
#define ps push
#define pp pop

using namespace std;

void get(int &a) {
	char c; a=0;
	do {c=getchar_unlocked();} while ('0'>c || c>'9');
	do {a*=10; a+=c^'0'; c=getchar_unlocked();} while ('0'<=c && c<='9');
}

int go(const int &n, const int &m, const vector <vector<vector<bool>>> &t, int r, pair <int,int> s, pair <int,int> e) {

	vector <vector<bool>> v(n+1,vector<bool>(m+1));

	priority_queue <pair<int,pair<int,int>>> q;

	q.ps({-r,s});

	while (!q.empty()) {

		pair <int,int> a = q.tp.ss;
		int b = -q.tp.ff;
		q.pp();

		if (!v[a.ff][a.ss]) {

			v[a.ff][a.ss] = 1;

			if (a.ff == e.ff && a.ss == e.ss) {
				return b;
			}

			if (a.ss+1 <= m && !v[a.ff][a.ss+1]) {

				int c=b;
				while (
					(a.ff == 0 || t[a.ff-1][a.ss][c%(int)t[a.ff-1][a.ss].sz]==0) &&
					(a.ff == n || t[a.ff][a.ss][c%(int)t[a.ff][a.ss].sz]==0)
				) {
					c++;
				}

				q.ps({-c,{a.ff,a.ss+1}});

			}

			if (a.ff+1 <= n && !v[a.ff+1][a.ss]) {

				int c=b;
				while (
					(a.ss == 0 || t[a.ff][a.ss-1][c%(int)t[a.ff][a.ss-1].sz]==1) &&
					(a.ss == m || t[a.ff][a.ss][c%(int)t[a.ff][a.ss].sz]==1)
				) {
					c++;
				}

				q.ps({-c,{a.ff+1,a.ss}});

			}

			if (a.ss-1 >= 0 && !v[a.ff][a.ss-1]) {

				int c=b;
				while (
					(a.ff == 0 || t[a.ff-1][a.ss-1][c%(int)t[a.ff-1][a.ss-1].sz]==0) &&
					(a.ff == n || t[a.ff][a.ss-1][c%(int)t[a.ff][a.ss-1].sz]==0)
				) {
					c++;
				}

				q.ps({-c,{a.ff,a.ss-1}});

			}

			if (a.ff-1 >= 0 && !v[a.ff-1][a.ss]) {

				int c=b;
				while (
					(a.ss == 0 || t[a.ff-1][a.ss-1][c%(int)t[a.ff-1][a.ss-1].sz]==1) &&
					(a.ss == m || t[a.ff-1][a.ss][c%(int)t[a.ff-1][a.ss].sz]==1)
				) {
					c++;
				}

				q.ps({-c,{a.ff-1,a.ss}});

			}

		}

	}

	return 0;

}

int main() {
	int n,m,q;
	get(n); get(m); get(q);

	vector <vector<vector<bool>>> t(n,vector<vector<bool>>(m));

	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			char c;
			do {c=getchar_unlocked();} while (c != '0' && c != '1');
			do {t[i][j].pb(c^'0'); c=getchar_unlocked();} while (c == '0' || c == '1');
		}
	}

	while (q--) {

		int r,a,b,c,d;

		get(r); get(a); get(b); get(c); get(d);

		printf("%d\n",go(n,m,t,r,{a,b},{c,d}));

	}

	return 0;
}