#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
const int INF = 1e9;
int n, m, k, q, chk[2020][2020], d[2020][2020], p[200200];
char s[2020][2020];
queue<array<int, 2>> qu;
vector<array<int, 3>> v, v2;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
bool merge(int x, int y) {
if((x = find(x)) == (y = find(y))) return 0;
p[x] = y;
return 1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k >> q;
for(int i=1;i<=n;i++) cin >> s[i]+1;
for(int i=1;i<=k;i++) {
int x, y; cin >> x >> y;
chk[x][y] = i, qu.push({x, y});
}
while(!qu.empty()) {
auto [x, y] = qu.front(); qu.pop();
int c = chk[x][y], p = d[x][y];
for(int i=0;i<4;i++) {
int xx = x+dx[i], yy = y+dy[i];
if(xx < 1 || yy < 1 || xx > n || yy > m || s[xx][yy] == '#') continue;
if(chk[xx][yy]) {
v.push_back({p+d[xx][yy], c, chk[xx][yy]});
} else {
chk[xx][yy] = c, d[xx][yy] = p+1, qu.push({xx, yy});
}
}
}
sort(v.begin(), v.end()), iota(p+1, p+1+k, 1);
for(auto V : v) if(merge(V[1], V[2])) v2.push_back(V);
swap(v, v2);
vector<array<int, 5>> t(q);
for(auto &[l, r, s, e, id] : t) cin >> s >> e, l = 0, r = 1e9;
for(int i=0;i<q;i++) t[i][4] = i;
int flag = 1;
while(flag--) {
iota(p+1, p+1+k, 1);
sort(t.begin(), t.end());
int i = 0;
for(auto &[l, r, s, e, id] : t) if(l <= r) {
flag = 1;
int m = (l+r) >> 1;
while(i < v.size() && v[i][0] <= m) merge(v[i][1], v[i][2]), i++;
if(find(s) == find(e)) r = m-1;
else l = m+1;
}
}
vector<int> ans(q);
for(auto [l, r, s, e, id] : t) ans[id] = (l >= INF ? -1 : l);
for(int i=0;i<q;i++) cout << ans[i] << "\n";
}
