#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX = 4000007, LIM = 200007;
char C[MAX];
int pv[MAX], D[MAX], R[LIM], P[LIM];
pii LR[LIM], QS[LIM];
int Find(int n) {
if (n == R[n]) return n;
return R[n] = Find(R[n]);
}
void Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return;
R[b] = a;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, M, K, T;
cin >> N >> M >> K >> T;
for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> C[i * M + j];
for (int i = 1; i <= K; ++i) {
int a, b;
cin >> a >> b; a--; b--;
P[i] = a * M + b;
}
vector<int> mv = {1, -1};
mv.push_back(M); mv.push_back(-M);
memset(D, 0x3f, sizeof(D));
queue<int> Q;
for (int i = 1; i <= K; ++i) {
D[P[i]] = 0;
pv[P[i]] = i;
Q.push(P[i]);
}
vector<pair<int, pii>> E;
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
for (int k = 0; k < 4; ++k) {
int next = cur + mv[k];
if (k == 0 && next % M == 0) continue;
if (k == 1 && cur % M == 0) continue;
if (next < 0 || N * M <= next) continue;
if (C[next] == '#') continue;
if (D[next] > 1e9) {
D[next] = D[cur] + 1;
pv[next] = pv[cur];
Q.push(next);
}
else if (pv[cur] != pv[next]) {
E.emplace_back(D[cur] + D[next], pii{pv[cur], pv[next]});
}
}
}
// Does sorting necessary?
sort(E.begin(), E.end());
vector<pair<int, pii>> TE;
iota(R, R + LIM, 0);
for (auto [n, p] : E) {
auto [a, b] = p;
if (Find(a) != Find(b)) {
TE.emplace_back(n, p);
Union(a, b);
}
}
swap(E, TE); TE.clear();
E.emplace_back(1e9, pii{1, 1});
for (int i = 1; i <= T; ++i) cin >> QS[i].first >> QS[i].second;
fill(LR, LR + LIM, pii{-1, MAX});
while (1) {
vector<pii> cand;
for (int i = 1; i <= T; ++i) {
auto [l, r] = LR[i];
if (l + 1 < r) cand.emplace_back((l + r) >> 1, i);
}
if (cand.empty()) break;
sort(cand.begin(), cand.end());
iota(R, R + LIM, 0);
int aidx = 0, bidx = 0;
while (aidx < E.size()) {
while (bidx < cand.size() && cand[bidx].first < E[aidx].first) {
auto [mid, id] = cand[bidx++];
auto [a, b] = QS[id];
(Find(a) == Find(b) ? LR[id].second : LR[id].first) = mid;
}
auto [c, d] = E[aidx++].second;
Union(c, d);
}
}
for (int i = 1; i <= T; ++i) {
int ans = LR[i].second;
if (ans == MAX) ans = -1;
cout << ans << '\n';
}
return 0;
}
