#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=1010000,M=15100;
int n,m,q,len[N];
char s[N][10];
int cutrow[M],cutcol[M];
const int TM=840,T1=15,T2=TM/T1;
const int R=(T2+5)*M,LOG=17;
typedef int matrix[M][880];
matrix rowu,rowd,coll,colr;
struct fuck {
	int par[R][LOG+1];
	int tt;
	void set(int u,int v) {
		par[u][0]=v;
	}
	void build(int ty,int n) {
		rep(j,1,LOG) rep(i,0,n) par[i][j]=par[par[i][j-1]][j-1];
		tt=ty;
	}
	int query(int x1,int t,int x2,matrix go) {
		int r=t%TM;
		int cc=(T1-r%T1)%T1;
		rep(rd,0,cc) {
			x1=go[x1][r];
			if ((tt==1&&x1>=x2)||(tt==0&&x1<=x2)) return t;
			r+=1; if (r==TM) r=0;
			t+=1;
		}
		int fx=x1*T2+(r/T1);
		per(j,0,LOG) {
			int v=par[fx][j];
			if ((tt==0&&v>=(x2+1)*T2)||(tt==1&&v<x2*T2)) {
				t+=(1<<j)*T1;
				fx=v;
			}
		}
		x1=fx/T2;
		r=t%TM;
		while (1) {
			x1=go[x1][r];
			if ((tt==1&&x1>=x2)||(tt==0&&x1<=x2)) return t;
			r+=1; if (r==TM) r=0;
			t+=1;
		}
		return t;
	}
}f[4];

namespace fastIO{ 
	#define BUF_SIZE 100000 
	#define OUT_SIZE 100000 
	#define ll long long 
	//fread->read 
	bool IOerror=0; 
	inline char nc(){ 
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
		if (p1==pend){ 
			p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
			if (pend==p1){IOerror=1;return -1;} 
			//{printf("IO error!\n");system("pause");for (;;);exit(0);} 
		} 
		return *p1++; 
	} 
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
	inline void read(int &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (sign)x=-x; 
	} 
	inline void read(ll &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (sign)x=-x; 
	} 
	inline void read(double &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (ch=='.'){ 
			double tmp=1; ch=nc(); 
			for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); 
		} 
		if (sign)x=-x; 
	} 
	inline void read(char *s){ 
		char ch=nc(); 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; 
		*s=0; 
	} 
	inline void read(char &c){ 
		for (c=nc();blank(c);c=nc()); 
		if (IOerror){c=-1;return;} 
	} 
	//getchar->read 
	inline void read1(int &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (bo)x=-x; 
	} 
	inline void read1(ll &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (bo)x=-x; 
	} 
	inline void read1(double &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (ch=='.'){ 
			double tmp=1; 
			for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar()); 
		} 
		if (bo)x=-x; 
	} 
	inline void read1(char *s){ 
		char ch=getchar(); 
		for (;blank(ch);ch=getchar()); 
		for (;!blank(ch);ch=getchar())*s++=ch; 
		*s=0; 
	} 
	inline void read1(char &c){for (c=getchar();blank(c);c=getchar());} 
	//scanf->read 
	inline void read2(int &x){scanf("%d",&x);} 
	inline void read2(ll &x){ 
		#ifdef _WIN32 
			scanf("%I64d",&x); 
		#else 
		#ifdef __linux 
			scanf("%lld",&x); 
		#else 
			puts("error:can't recognize the system!"); 
		#endif 
		#endif 
	} 
	inline void read2(double &x){scanf("%lf",&x);} 
	inline void read2(char *s){scanf("%s",s);} 
	inline void read2(char &c){scanf(" %c",&c);} 
	//inline void readln2(char *s){gets(s);} 
	//fwrite->write 
	struct Ostream_fwrite{ 
		char *buf,*p1,*pend; 
		Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} 
		void out(char ch){ 
			if (p1==pend){ 
				fwrite(buf,1,BUF_SIZE,stdout);p1=buf; 
			} 
			*p1++=ch; 
		} 
		void print(int x){ 
			static char s[15],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); 
		} 
		void println(int x){ 
			static char s[15],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); out('\n'); 
		} 
		void print(ll x){ 
			static char s[25],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); 
		} 
		void println(ll x){ 
			static char s[25],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); out('\n'); 
		} 
		void print(double x,int y){ 
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000, 
				1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL, 
				100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL}; 
			if (x<-1e-12)out('-'),x=-x;x*=mul[y]; 
			ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1; 
			ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2); 
			if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];++i) out('0'); print(x3);} 
		} 
		void println(double x,int y){print(x,y);out('\n');} 
		void print(char *s){while (*s)out(*s++);} 
		void println(char *s){while (*s)out(*s++);out('\n');} 
		void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}} 
		~Ostream_fwrite(){flush();} 
	}Ostream; 
	inline void print(int x){Ostream.print(x);} 
	inline void println(int x){Ostream.println(x);} 
	inline void print(char x){Ostream.out(x);} 
	inline void println(char x){Ostream.out(x);Ostream.out('\n');} 
	inline void print(ll x){Ostream.print(x);} 
	inline void println(ll x){Ostream.println(x);} 
	inline void print(double x,int y){Ostream.print(x,y);} 
	inline void println(double x,int y){Ostream.println(x,y);} 
	inline void print(char *s){Ostream.print(s);} 
	inline void println(char *s){Ostream.println(s);} 
	inline void println(){Ostream.out('\n');} 
	inline void flush(){Ostream.flush();} 
	//puts->write 
	char Out[OUT_SIZE],*o=Out; 
	inline void print1(int x){ 
		static char buf[15]; 
		char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x; 
		while(x)*p1++=x%10+'0',x/=10; 
		while(p1--!=buf)*o++=*p1; 
	} 
	inline void println1(int x){print1(x);*o++='\n';} 
	inline void print1(ll x){ 
		static char buf[25]; 
		char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x; 
		while(x)*p1++=x%10+'0',x/=10; 
		while(p1--!=buf)*o++=*p1; 
	} 
	inline void println1(ll x){print1(x);*o++='\n';} 
	inline void print1(char c){*o++=c;} 
	inline void println1(char c){*o++=c;*o++='\n';} 
	inline void print1(char *s){while (*s)*o++=*s++;} 
	inline void println1(char *s){print1(s);*o++='\n';} 
	inline void println1(){*o++='\n';} 
	inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}} 
	struct puts_write{ 
		~puts_write(){flush1();} 
	}_puts; 
	inline void print2(int x){printf("%d",x);} 
	inline void println2(int x){printf("%d\n",x);} 
	inline void print2(char x){printf("%c",x);} 
	inline void println2(char x){printf("%c\n",x);} 
	inline void print2(ll x){ 
		#ifdef _WIN32 
			printf("%I64d",x); 
		#else 
		#ifdef __linux 
			printf("%lld",x); 
		#else 
			puts("error:can't recognize the system!"); 
		#endif 
		#endif 
	} 
	inline void println2(ll x){print2(x);printf("\n");} 
	inline void println2(){printf("\n");} 
	#undef ll 
	#undef OUT_SIZE 
	#undef BUF_SIZE 
}; 
using namespace fastIO; 

int rowc[M][9][9],colc[M][9][9];

int main() {
	read(n); read(m); read(q);
	rep(i,0,n*m) {
		read(s[i]);
		len[i]=strlen(s[i]);
		int rr=i/m,cc=i%m;
		rep(j,0,len[i]) rowc[rr][len[i]][j]+=(s[i][j]=='0');
		rep(j,0,len[i]) colc[cc][len[i]][j]+=(s[i][j]=='1');
	}
	rep(T,0,TM) {
		rep(i,0,n) {
			cutrow[i]=1;
			rep(k,2,9) cutrow[i]&=(rowc[i][k][T%k]==0);
		}
		rep(j,0,m) {
			cutcol[j]=1;
			rep(k,2,9) cutcol[j]&=(colc[j][k][T%k]==0);
		}
		rep(i,0,n+1) {
			rowu[i][T]=(i==0)?0:cutrow[i-1]?i:rowu[i-1][T];
		}
		per(i,0,n+1) {
			rowd[i][T]=(i==n)?n:cutrow[i]?i:rowd[i+1][T];
		}
		rep(i,0,m+1) {
			coll[i][T]=(i==0)?0:cutcol[i-1]?i:coll[i-1][T];
		}
		per(i,0,m+1) {
			colr[i][T]=(i==m)?m:cutcol[i]?i:colr[i+1][T];
		}
	}
	rep(T,0,TM) if (T%T1==0) {
		rep(i,0,n+1) {
			int p1=i,p2=i,tt=T;
			rep(j,0,T1) {
				p1=rowu[p1][tt]; p2=rowd[p2][tt];
				tt=(tt+1)%TM;
			}
			f[0].set(i*T2+(T/T1),p1*T2+(tt/T1));
			f[1].set(i*T2+(T/T1),p2*T2+(tt/T1));
		}

		rep(i,0,m+1) {
			int p1=i,p2=i,tt=T;
			rep(j,0,T1) {
				p1=coll[p1][tt]; p2=colr[p2][tt];
				tt=(tt+1)%TM;
			}
			//printf("zz %d %d\n",i,p1);
			f[2].set(i*T2+(T/T1),p1*T2+(tt/T1));
			f[3].set(i*T2+(T/T1),p2*T2+(tt/T1));
		}
	}
	f[0].build(0,(n+1)*T2);
	f[1].build(1,(n+1)*T2);
	f[2].build(0,(m+1)*T2);
	f[3].build(1,(m+1)*T2);
	rep(i,0,q) {
		int tt,x1,y1,x2,y2;
		read(tt); read(x1); read(y1); read(x2); read(y2);
		int ans=tt;
		if (x2>x1) ans=max(ans,f[1].query(x1,tt,x2,rowd));
		if (x2<x1) ans=max(ans,f[0].query(x1,tt,x2,rowu));
		if (y2>y1) ans=max(ans,f[3].query(y1,tt,y2,colr));
		if (y2<y1) ans=max(ans,f[2].query(y1,tt,y2,coll));
		println(ans);
		//printf("%d\n",ans);
	}
}