#include <bits/stdc++.h> using namespace std; using pint = pair<int, int>; #define all(x) x.begin(), x.end() const int D[]{0, 1, 0, -1}; struct DSU { int par[200001]; DSU() { memset(par, -1, sizeof par); } int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); } void merge(int a, int b) { if ((a = find(a)) == (b = find(b))) return; if (-par[a] > -par[b]) swap(a, b); par[b] += par[a]; par[a] = b; } }; vector<pint> adj[200001]; int jump[200001][18][2], dep[200001]; void dfs(int i, int p = 0) { for (auto [j, d]: adj[i]) { if (j == p) continue; dep[j] = dep[i] + 1; jump[j][0][0] = i, jump[j][0][1] = d; dfs(j, i); } } int main() { int R, C, p, Q; cin >> R >> C >> p >> Q; int seen[R][C]; for (auto &row: seen) { for (auto &b: row) { char c; cin >> c; b = c == '.' ? 0 : -1; } } queue<pair<pint, int>> q; for (int i = 1; i <= p; ++i) { int r, c; cin >> r >> c; --r, --c; q.push({{r, c}, seen[r][c] = i}); } DSU dsu; int t[R][C]{}; vector<array<int, 3>> edges; while (not q.empty()) { auto [loc, i] = q.front(); auto [r, c] = loc; q.pop(); for (int j = 4; j--;) { int r2 = r + D[j], c2 = c + D[j ^ 1]; if (r2 < 0 or r2 >= R or c2 < 0 or c2 >= C) continue; if (not seen[r2][c2]) { q.push({{r2, c2}, seen[r2][c2] = i}); t[r2][c2] = t[r][c] + 1; } else if (~seen[r2][c2] and seen[r2][c2] != i) edges.push_back({t[r2][c2] + t[r][c], seen[r2][c2], i}); } } sort(all(edges)); for (auto &[w, u, v]: edges) { if (dsu.find(u) != dsu.find(v)) { adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); dsu.merge(u, v); } } for (int i = 1; i <= p; ++i) { if (dsu.find(i) == i) dfs(i); } for (int j = 1; j < 18; ++j) { for (int i = 1; i <= p; ++i) { jump[i][j][0] = jump[jump[i][j - 1][0]][j - 1][0]; jump[i][j][1] = max(jump[i][j - 1][1], jump[jump[i][j - 1][0]][j - 1][1]); } } while (Q--) { int i, j; cin >> i >> j; if (dsu.find(i) == dsu.find(j)) { int ans = 0; if (dep[i] > dep[j]) swap(i, j); for (int k = 18; k--;) { if (dep[j] - (1 << k) >= dep[i]) { ans = max(ans, jump[j][k][1]); j = jump[j][k][0]; } } for (int k = 18; k--;) { if (jump[i][k][0] != jump[j][k][0]) { ans = max({ans, jump[i][k][1], jump[j][k][1]}); i = jump[i][k][0]; j = jump[j][k][0]; } } if (i != j) ans = max({ans, jump[i][0][1], jump[j][0][1]}); cout << ans << endl; } else cout << "-1\n"; } }