#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Fin(file) freopen(file".in","r",stdin)
#define Fout(file) freopen(file".out","w",stdout)
#define Fgen(file) freopen(file".in","w",stdout)
#define Fans(file) freopen(file".ans","w",stdout)
// #define int long long
using namespace std;

const int N=1e6+5,M=15005,K=840;

// template < class T, int SZ >
// class Myvector{
//     int nxt[SZ],tot;
//     T val[SZ];
    
// public:
    
//     void clear() { tot=0; }
    
//     int newhead() { return ++tot; }
    
//     void add(int& h,const T& v)
//     {
//         nxt[++tot]=h;
//         h=tot;
//         val[tot]=v;
//     }
    
//     T& get(int p) { return val[p]; }
    
//     int next(int p) { return nxt[p]; }
// };

// #define ForMyvector(vec,head,obj)\
// obj=vec.get(head); for(int _o=head; _o; _o=vec.next(_o),obj=vec.get(_o))


struct Query{
    int id,cp;
};

char s[N][12];
int n,m,Q,len[N];
int cut[K][M];
int type[K];
int nxtcon[K];
int qx1[N],qx2[N],qdir[N],qtim[N],qrealtim[N],ans[N];
// vector<int> son[K][M];
// vector<Query> qry[K][M];
int son[K][M];
// int qid[K][M],qcp[K][M];
// Myvector<Query,K*M> qry;
vector<Query> qry[K][M];
int dep[K*M];

int num(int i,int j)
{
    return (i-1)*m+j;
}

void dfs(int t,int u,int d,int op)
{
    dep[u]=d;
    
    // if(qid[t][u]){
    //     ans[qid[t][u]]=min(ans[qid[t][u]],d-dep[qcp[t][u]]);
    // }
    for(auto qr:qry[t][u]){
        ans[qr.id]=min(ans[qr.id],d-dep[qr.cp]);
    }
    
    if(son[t][u]&2){
        dfs((t-1+840)%840,u,d+1,op);
        dep[u]=d;
    }
    if(son[t][u]&1){
        dfs(t,u+op,d,op);
        dep[u]=d;
    }
}

void solve0()
{
    clr(son,0);
    For(t,0,839) For(i,0,n) qry[t][i].clear();
    
    For(t,0,839){
        For(i,0,n-1){
            if(type[t]==0 && cut[t][i+1]){
                son[(t+1)%840][i]|=2;
            }
            else{
                son[t][i+1]|=1;
            }
        }
    }
    
    For(i,1,Q) if(qdir[i]==0){
        int x1=qx1[i],x2=qx2[i],t=qtim[i];
        
        qry[t][x1].push_back({i,x2});
    }
    
    For(t,0,839) dfs(t,n,0,-1);
}

void solve1()
{
    clr(son,0);
    For(t,0,839) For(i,0,n) qry[t][i].clear();
    
    For(t,0,839){
        For(i,1,n){
            if(type[t]==0 && cut[t][i]){
                son[(t+1)%840][i]|=2;
            }
            else{
                son[t][i-1]|=1;
            }
        }
    }
    
    For(i,1,Q) if(qdir[i]==1){
        int x1=qx1[i],x2=qx2[i],t=qtim[i];
        
        qry[t][x1].push_back({i,x2});
    }
    
    For(t,0,839) dfs(t,0,0,1);
}

void solve2()
{
    clr(son,0);
    For(t,0,839) For(i,0,m) qry[t][i].clear();
    
    For(t,0,839){
        For(i,0,m-1){
            if(type[t]==1 && cut[t][i+1]){
                son[(t+1)%840][i]|=2;
            }
            else{
                son[t][i+1]|=1;
            }
        }
    }
    
    For(i,1,Q) if(qdir[i]==2){
        int x1=qx1[i],x2=qx2[i],t=qtim[i];
        
        qry[t][x1].push_back({i,x2});
    }
    
    For(t,0,839) dfs(t,m,0,-1);
}

void solve3()
{
    clr(son,0);
    For(t,0,839) For(i,0,m) qry[t][i].clear();
    
    For(t,0,839){
        For(i,1,m){
            if(type[t]==1 && cut[t][i]){
                son[(t+1)%840][i]|=2;
            }
            else{
                son[t][i-1]|=1;
            }
        }
    }
    
    For(i,1,Q) if(qdir[i]==3){
        int x1=qx1[i],x2=qx2[i],t=qtim[i];
        
        qry[t][x1].push_back({i,x2});
    }
    
    For(t,0,839) dfs(t,0,0,1);
}


int read()
{
    char Charlie;
    while((Charlie=getchar())<'0'||Charlie>'9') ;
    int Vinnie=Charlie-'0';
    while((Charlie=getchar())>='0'&&Charlie<='9') Vinnie=(Vinnie<<3)+(Vinnie<<1)+Charlie-'0';
    return Vinnie;
}

signed main()
{
    // Fin("J");
    // Fout("J");
    
    n=read(); m=read(); Q=read();
    
    For(i,1,n) For(j,1,m){
        int o=num(i,j);
        scanf(" %s",s[o]);
        len[o]=strlen(s[o]);
    }
    
    For(t,0,839){
        // Try to cut horizotally first
        
        type[t]=0;
        
        int flg=0;
        
        For(i,1,n){
            int ok=1;
            For(j,1,m){
                int o=num(i,j);
                if(s[o][t%len[o]]=='0'){
                    ok=0; break;
                }
            }
            if(ok) { cut[t][i]=1; flg=1; }
        }
        
        if(!flg){
            // If fail, then cut vertically
            
            type[t]=1;
            
            For(j,1,m){
                int ok=1;
                For(i,1,n){
                    int o=num(i,j);
                    if(s[o][t%len[o]]=='1'){
                        ok=0; break;
                    }
                }
                if(ok) { cut[t][j]=1; flg=1; }
            }
            
            if(!flg) type[t]=2;
        }
    }
    
    clr(nxtcon,0x3f);
    
    int all_same=1;
    For(t,0,839){
        if(type[t]!=type[0]){
            all_same=0; break;
        }
    }
    
    if(!all_same){
        For(t,0,839){
            if(type[t]==2){
                nxtcon[t]=0; continue;
            }
            
            int t0;
            for(t0=(t+1)%840;type[t0]==type[t];t0=(t0+1)%840) ;
            
            nxtcon[t]=(t0-t+840)%840;
        }
    }
    
    cerr<<"befor query: "<<clock()<<endl;
    
    For(i,1,Q){
        int t,x1,y1,x2,y2;
        t=read(); x1=read(); y1=read(); x2=read(); y2=read();
        
        qrealtim[i]=t;
        t%=840;
        qtim[i]=t;
        
        if(type[t]==2){
            qdir[i]=-1;
            ans[i]=0;
            continue;
        }
        
        if(type[t]==0){
            qx1[i]=x1; qx2[i]=x2;
            ans[i]=nxtcon[t];
            if(x1<x2) qdir[i]=0;
            else qdir[i]=1;
        }
        else{
            qx1[i]=y1; qx2[i]=y2;
            ans[i]=nxtcon[t];
            if(y1<y2) qdir[i]=2;
            else qdir[i]=3;
        }
    }
    
    cerr<<"before solve0: "<<clock()<<endl;
    solve0();
    cerr<<"before solve1: "<<clock()<<endl;
    solve1();
    cerr<<"before solve2: "<<clock()<<endl;
    solve2();
    cerr<<"before solve3: "<<clock()<<endl;
    solve3();
    
    For(i,1,Q) printf("%d\n",qrealtim[i]+ans[i]);
    
    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}

/*
10 10 1
0001000 0001000 00100 0001000 10000000 10000000 00100 0001000 0001000 000010
0001000 0001000 0001000 00001 0001000 0001000 100000 0001000 0001000 00001
00000001 00001 0001000 00001 0001000 00001 0001000 00001 0001000 000010
0001000 0001000 000001 0001000 0001000 0001000 0001000 0001000 0001000 0001000
0001000 0001000 0001000 0001000 0001000 0001000 100000 100000 0001000 0001000
00000001 0001000 0001000 00001 0001000 00001 0001000 00001 00001 0001000
0001000 0001000 0001000 0001000 10000000 000010 0001000 0001000 0001000 0001000
0001000 00001 0001000 00001 10000000 00001 0001000 0001000 0001000 00001
100000 00001 0001000 00001 0001000 0001000 0001000 00001 0001000 0001000
0001000 00001 0001000 00001 0001000 00001 0001000 100000 0001000 00001
265353479 7 1 0 9
*/

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/