#include <bits/stdc++.h>

#define ____AnhKietSS____ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define NamDinh signed
#define ii pair<int,int>
#define ll long long
#define foru(i,d,c) for(int i=(d);i<=(c);i++)
#define ford(i,d,c) for(int i=(d);i>=(c);i--)
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

const ll INF=4557430888798830399LL;

struct Edge
{
    int v;
    ll w;
};

int n,m,k,q;
vector<vector<Edge> > a;

int id(int r,int c)
{
    return r*m+c;
}

ll dijkstra(int s,int t)
{
    if(s==t)return 0;

    vector<ll> d(n*m,INF);
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;

    d[s]=0;
    pq.push({0,s});

    while(!pq.empty())
    {
        ll du=pq.top().fi;
        int u=pq.top().se;
        pq.pop();

        if(du!=d[u])continue;
        if(u==t)return du;

        for(int i=0;i<(int)a[u].size();i++)
        {
            int v=a[u][i].v;
            ll w=a[u][i].w;

            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                pq.push({d[v],v});
            }
        }
    }

    return -1;
}

NamDinh main()
{
    ____AnhKietSS____

    freopen("MAZE.INP","r",stdin);
    freopen("MAZE.OUT","w",stdout);

    cin>>n>>m>>k>>q;

    vector<string> s(n);
    foru(i,0,n-1)cin>>s[i];

    a.resize(n*m);

    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};

    foru(i,0,n-1)
    {
        foru(j,0,m-1)
        {
            if(s[i][j]=='#')continue;

            int u=id(i,j);

            foru(z,0,3)
            {
                int x=i+dx[z];
                int y=j+dy[z];

                if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.')
                {
                    int v=id(x,y);
                    a[u].pb({v,1});
                }
            }
        }
    }

    foru(i,1,k)
    {
        int x,y,u,v;
        ll w;

        cin>>x>>y>>u>>v>>w;

        --x;
        --y;
        --u;
        --v;

        int p=id(x,y);
        int t=id(u,v);

        a[p].pb({t,w});
        a[t].pb({p,w});
    }

    while(q--)
    {
        int x,y,u,v;

        cin>>x>>y>>u>>v;

        --x;
        --y;
        --u;
        --v;

        int s1=id(x,y);
        int s2=id(u,v);

        cout<<dijkstra(s1,s2)<<"\n";
    }

    return 0;
}