#include <stdio.h>
#include <string.h>
#define N 2000
#define P 200000
#define M 20000000
#define M1 300000
#define P_ (P + M1)
int n, m, p, q, qwq[N][N], d[N][N], x[P], y[P], qu[N * N], he, ta, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}
, uu[M], vv[M], ww[M], top, ii[M], ff[1 << 16]
, dfn[P_], dfc, fa[P_], hld[P_], lv[P_], ds[P_], ch[P_][2], l, stamp[P_];
char s[N][N + 1];
void ADD(int u, int v, int w) {
if (top == M)
__builtin_trap();
uu[top] = u, vv[top] = v, ww[top] = w;
++top;
}
void SORT() {
for (int i = 0; i < top; ++i)
++ff[ww[i]];
for (int i = 1; i < (1 << 16); ++i)
ff[i] += ff[i - 1];
for (int i = 0; i < top; ++i)
ii[--ff[ww[i]]] = i;
}
void Init() {
scanf("%d%d%d%d", &n, &m, &p, &q);
for (int i = 0; i < n; ++i)
scanf("%s", s[i]);
for (int i = 0; i < p; ++i)
scanf("%d%d", x + i, y + i), --x[i], --y[i];
}
void MakeGraph() {
for (int i = 0; i < p; ++i) {
qwq[x[i]][y[i]] = i + 1;
qu[he++] = x[i] * m + y[i];
}
for (int u, x, y; he ^ ta;) {
u = qu[ta++];
x = u / m, y = u % m;
for (int nx, ny , j = 0; j < 4; ++j) {
int nx = x + dx[j], ny = y + dy[j];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || s[nx][ny] == '#')
continue;
if (qwq[nx][ny]) {
ADD(qwq[nx][ny] - 1, qwq[x][y] - 1, d[nx][ny] + d[x][y]);
} else {
qwq[nx][ny] = qwq[x][y];
d[nx][ny] = d[x][y] + 1;
qu[he++] = nx * m + ny;
}
}
}
SORT();
}
int ds_find(int i) {
if (ds[i] < 0) return i;
return ds[i] = ds_find(ds[i]);
}
void dfs(int u) {
dfn[u] = ++dfc;
if (~ch[u][0]) {
hld[ch[u][0]] = hld[u];
lv[ch[u][0]] = lv[u] + 1;
dfs(ch[u][0]);
}
if (~ch[u][1]) {
hld[ch[u][1]] = ch[u][1];
lv[ch[u][1]] = lv[u] + 1;
dfs(ch[u][1]);
}
}
void MakeKRT() {
memset(ds, -1, sizeof ds);
memset(ch, -1, sizeof ch);
l = p;
for (int i, i_ = 0; i_ < top; ++i_) {
i = ii[i_];
if (ds_find(uu[i]) == ds_find(vv[i]))
continue;
uu[i] = ds_find(uu[i]), vv[i] = ds_find(vv[i]);
if (-ds[uu[i]] < -ds[vv[i]])
uu[i] ^= vv[i], vv[i] ^= uu[i], uu[i] ^= vv[i];
ch[l][0] = uu[i], ch[l][1] = vv[i];
ds[l] += ds[uu[i]] + ds[vv[i]];
fa[uu[i]] = fa[vv[i]] = l;
ds[uu[i]] = ds[vv[i]] = l;
stamp[l] = ww[i];
fa[l] = l;
++l;
}
for (int i = l - 1; i >= 0; --i) {
if (! dfn[i]) {
hld[i] = i;
lv[i] = 0;
dfs(i);
}
}
}
int lca(int u, int v) {
if (ds_find(u) != ds_find(v))
return -1;
while (hld[u] ^ hld[v]) {
if (lv[hld[u]] < lv[hld[v]]) u ^= v, v ^= u, u ^= v;
u = fa[hld[u]];
}
return dfn[u] < dfn[v] ? u : v;
}
void Answer() {
for (int x, s, t, i = 0; i < q; ++i) {
scanf("%d%d", &s, &t);
--s, --t;
x = lca(s, t);
if (! ~x)
puts("-1");
else
printf("%hd\n", stamp[x]);
}
}
int main() {
Init(), MakeGraph(), MakeKRT(), Answer();
return 0;
}
