#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mt make_tuple
const int M=2050;
const int N=200050;
const int L=19;
char base[M][M];
int dist[M][M],my[M][M];
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int par[N][L],mx[N][L],p[N];
int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
vector<int> E[N];
int dep[N];
void DFS(int u){ for(int v:E[u]) dep[v]=dep[u]+1,DFS(v);}
int LCA(int u, int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=L-1;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
for(int i=L-1;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
return u==v?v:par[v][0];
}
int Get(int u, int k)
{
int ans=0;
for(int i=0;i<L;i++) if(k>>i&1) ans=max(ans,mx[u][i]),u=par[u][i];
return ans;
}
int main()
{
int n,m,p,q;
scanf("%i %i %i %i",&n,&m,&p,&q);
for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
queue<int> qu;
for(int i=1,x,y;i<=p;i++)
{
scanf("%i %i",&x,&y);
my[x][y]=i;
qu.push(x*M+y);
}
while(qu.size())
{
int x=qu.front()/M,y=qu.front()%M;
qu.pop();
for(int i=0;i<4;i++)
{
int nx=x+mv[i][0];
int ny=y+mv[i][1];
if(base[nx][ny]=='.' && !my[nx][ny])
{
my[nx][ny]=my[x][y];
dist[nx][ny]=dist[x][y]+1;
qu.push(nx*M+ny);
}
}
}
vector<tuple<int,int,int>> edges;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]=='.')
{
for(int k=0;k<2;k++)
{
int x=i+mv[k][0];
int y=j+mv[k][1];
if(base[x][y]=='.' && my[x][y]!=my[i][j])
{
edges.pb(mt(dist[i][j]+dist[x][y],my[i][j],my[x][y]));
}
}
}
sort(edges.begin(),edges.end());
for(auto e:edges)
{
int w,u,v;tie(w,u,v)=e;
if(Find(u)!=Find(v))
{
::p[u=Find(u)]=v=Find(v);
par[u][0]=v;
mx[u][0]=w;
}
}
for(int j=1;j<L;j++) for(int i=1;i<=p;i++)
{
par[i][j]=par[par[i][j-1]][j-1];
mx[i][j]=max(mx[i][j-1],mx[par[i][j-1]][j-1]);
}
for(int i=1;i<=p;i++) E[par[i][0]].pb(i);
DFS(0);
while(q--)
{
int x,y;
scanf("%i %i",&x,&y);
int z=LCA(x,y);
if(z==0) printf("-1\n");
else printf("%i\n",max(Get(x,dep[x]-dep[z]),Get(y,dep[y]-dep[z])));
}
return 0;
}
