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
130
131
132
133
134
135
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=15e3;
const int NM=1e6;
const int Q=1e6;
const int S=8;
const int MOD=840;
bool bad[2][N+10][S+2][S+2]; //[0]-hor,[1]-ver; false-no way to walk across for pedestrians
bool crossable[2][N+10][MOD+10];
bool all_crossable[2][MOD+10];
int mvl[2][N+10][MOD+10];
int mvr[2][N+10][MOD+10];
int nxtl[2][N+10][2*MOD+10];
int nxtr[2][N+10][2*MOD+10];
int ans[Q+10];
int beg[Q+10];
int solve(int mod,int tt,int x1,int x2)
{
	if(x1==x2)
		return mod;
	int w=0;
	for(int i=mod,l=x1,r=x1;true;i++)
	{
		w+=(i/MOD)*MOD;
		i%=MOD;
		i=min(nxtl[tt][l][i],nxtr[tt][r][i]);
		l=mvl[tt][l][i%MOD];
		r=mvr[tt][r][i%MOD];
		if(l<=x2 && x2<=r)
			return w+i;
	}
	return -1;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m,q;
	cin>>n>>m>>q;

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			string s;
			cin>>s;
			for(size_t it=0;it<s.size();it++)
			{
				if(s[it]=='0')
					bad[0][i][s.size()][it]=true;
				else
					bad[1][j][s.size()][it]=true;
			}
		}
	}
	for(int j=0;j<MOD;j++)
		all_crossable[0][j]=all_crossable[1][j]=true;
	auto find_crossable=[&](int nn,bool tt)
	{
		for(int i=1;i<=nn;i++)
		{
			for(int j=0;j<MOD;j++)
			{
				for(int it=2;it<=S;it++)
				{
					if(bad[tt][i][it][j%it])
						crossable[tt][i][j]=true;
				}
				if(!crossable[tt][i][j])
					all_crossable[tt][j]=false;
			}
		}
		return;
	};
	find_crossable(n,0);
	find_crossable(m,1);
	for(bool tt:{0,1})
	{
		int nn=(tt ? m:n);
		for(int mod=0;mod<MOD;mod++)
		{
			mvr[tt][nn][mod]=nn;
			for(int i=nn-1;i>=0;i--)
			{
				if(crossable[tt][i+1][mod])
					mvr[tt][i][mod]=mvr[tt][i+1][mod];
				else
					mvr[tt][i][mod]=i;
			}
			mvl[tt][0][mod]=0;
			for(int i=1;i<=nn;i++)
			{
				if(crossable[tt][i][mod])
					mvl[tt][i][mod]=mvl[tt][i-1][mod];
				else
					mvl[tt][i][mod]=i;
			}
		}
		for(int i=0;i<=nn;i++)
		{
			nxtl[tt][i][2*MOD]=2*MOD;
			nxtr[tt][i][2*MOD]=2*MOD;
			for(int mod=2*MOD-1;mod>=0;mod--)
			{
				if(mvl[tt][i][mod%MOD]!=i)
					nxtl[tt][i][mod]=mod;
				else
					nxtl[tt][i][mod]=nxtl[tt][i][mod+1];
				if(mvr[tt][i][mod%MOD]!=i)
					nxtr[tt][i][mod]=mod;
				else
					nxtr[tt][i][mod]=nxtr[tt][i][mod+1];
			}
		}
	}

	for(int i=1;i<=q;i++)
	{
		int mod,a,b,c,d;
		cin>>mod>>a>>b>>c>>d;
		beg[i]=MOD*(mod/MOD);
		mod%=MOD;
		if(all_crossable[0][mod])
			ans[i]=solve(mod,1,b,d);
		else
			ans[i]=solve(mod,0,a,c);
	}

	for(int i=1;i<=q;i++)
		cout<<beg[i]+ans[i]<<"\n";
	return 0;
}