#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> trinca;
struct pergunta{
int ini,fim,meio,resp,idx,u,v;
pergunta(int _ini = 0,int _fim = 0,int _idx = 0,int _u = 0,int _v = 0){
ini = _ini;
fim = _fim;
idx = _idx;
resp = -1;
meio = -1;
u = _u;
v = _v;
}
bool operator<(const pergunta& other)const{
return meio < other.meio;
}
};
const int MAXL = 2010;
const int MAXN = 2*1e5 + 10;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
char entrada[MAXL][MAXL];
int grid[MAXL][MAXL],dist[MAXL][MAXL],H,W,P,Q,pai[MAXN];
int exibe[MAXN];
vector<trinca> Kruskal,MST;
vector<pergunta> D;
queue<ii> bfs;
int find(int x){
if(x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x,int y){
x = find(x);
y = find(y);
if(x == y) return;
if(x > y) swap(x,y);
pai[y] = x;
}
inline int valido(int x,int y){
return x >= 0 && x < H && y >= 0 && y < W && entrada[x][y] != '#';
}
void reseta_dsu(){
for(int i = 1;i<=P;i++) pai[i] = i;
}
int main(){
scanf("%d %d %d %d",&H,&W,&P,&Q);
for(int i = 0;i<H;i++){
scanf("%s",entrada[i]);
}
for(int i = 1;i<=P;i++){
int x,y;
scanf("%d %d",&x,&y);
x--;y--;
grid[x][y] = i;
bfs.push({x,y});
}
for(int i = 1;i<=Q;i++){
int u,v;
scanf("%d %d",&u,&v);
pergunta davez(0,P-2,i,u,v);
D.push_back(davez);
}
while(!bfs.empty()){
int x = bfs.front().first,y = bfs.front().second;
bfs.pop();
for(int i = 0;i<4;i++){
int nx = x + dx[i],ny = y + dy[i];
if(!valido(nx,ny) || grid[nx][ny] != 0) continue;
grid[nx][ny] = grid[x][y];
dist[nx][ny] = dist[x][y] + 1;
bfs.push({nx,ny});
}
}
for(int i = 0;i<H;i++){
for(int j = 0;j < W;j++){
if(!valido(i,j)) continue;
if(valido(i+1,j) && grid[i][j] != grid[i+1][j]){
Kruskal.push_back({dist[i][j] + dist[i+1][j], grid[i][j], grid[i+1][j] });
}
if(valido(i,j+1) && grid[i][j] != grid[i][j+1]){
Kruskal.push_back({dist[i][j] + dist[i][j+1],grid[i][j], grid[i][j+1]});
}
}
}
sort(Kruskal.begin(),Kruskal.end());
reseta_dsu();
for(int i = 0;i<Kruskal.size();i++){
int u = get<1>(Kruskal[i]),v = get<2>(Kruskal[i]);
if(find(u) != find(v)){
join(u,v);
MST.push_back(Kruskal[i]);
}
}
for(int iteracao = 1;iteracao <= 19;iteracao++){
int meu_ptr = 0;
for(int i = 0;i<D.size();i++){
if(D[i].ini > D[i].fim){
D[i].meio = P;
}
else{
D[i].meio = (D[i].ini + D[i].fim)/2;
}
}
reseta_dsu();
sort(D.begin(),D.end());
for(int i = 0;i<D.size();i++){
if(D[i].meio == P) break;
while(meu_ptr < MST.size() && meu_ptr <= D[i].meio){
join(get<1>(MST[meu_ptr]),get<2>(MST[meu_ptr]));
meu_ptr++;
}
if(find(D[i].u) == find(D[i].v)){
D[i].resp = D[i].meio;
D[i].fim = D[i].meio - 1;
}
else{
D[i].ini = D[i].meio + 1;
}
}
}
for(int i = 0;i<D.size();i++) exibe[D[i].idx] = D[i].resp;
for(int i = 1;i<=Q;i++){
if(exibe[i] == -1) printf("-1\n");
else printf("%d\n",get<0>(MST[exibe[i]]));
}
return 0;
}
