#include <stdio.h>
#include <string.h>
#define N 2000
#define M 2000
#define N_ 200000
#define M_ (N * M * 4)
#define INF 0x3f3f3f3f
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int uu[M_], vv[M_], ww[M_], m_;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[hh[j]] == ww[h])
j++;
else if (ww[hh[j]] < ww[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int ds[N_], ww_[N_];
int find(int i) {
return ds[i] < 0 ? i : find(ds[i]);
}
void join(int i, int j, int w) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j, ww_[i] = w;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, ww_[j] = w;
}
}
int query(int i, int j) {
int w = 0;
while (i != j && (ww_[i] != INF || ww_[j] != INF))
if (ww_[i] < ww_[j])
w = ww_[i], i = ds[i];
else
w = ww_[j], j = ds[j];
return i != j ? -1 : w;
}
int main() {
static char cc[N][M + 1];
static int dd[N][M], uu_[N][M], qu[N * M], hh[M_];
int n, n_, m, q, h, i, j, u, v, head, cnt;
scanf("%d%d%d%d", &n, &m, &n_, &q);
for (i = 0; i < n; i++)
scanf("%s", cc[i]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
dd[i][j] = n * m, uu_[i][j] = -1;
head = cnt = 0;
for (u = 0; u < n_; u++) {
scanf("%d%d", &i, &j), i--, j--;
dd[i][j] = 0, uu_[i][j] = u, qu[head + cnt++] = i * m + j;
}
while (cnt) {
int ij, d;
ij = qu[cnt--, head++], i = ij / m, j = ij % m, d = dd[i][j] + 1, u = uu_[i][j];
for (h = 0; h < 4; h++) {
int i_ = i + di[h], j_ = j + dj[h];
if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == '.') {
if (dd[i_][j_] > d)
dd[i_][j_] = d, uu_[i_][j_] = u, qu[head + cnt++] = i_ * m + j_;
else if ((v = uu_[i_][j_]) != u)
uu[m_] = u, vv[m_] = v, ww[m_] = d + dd[i_][j_] - 1, m_++;
}
}
}
for (h = 0; h < m_; h++)
hh[h] = h;
sort(hh, 0, m_);
memset(ds, -1, n_ * sizeof *ds);
memset(ww_, 0x3f, n_ * sizeof *ww_);
for (h = 0; h < m_; h++)
join(uu[hh[h]], vv[hh[h]], ww[hh[h]]);
while (q--) {
scanf("%d%d", &i, &j), i--, j--;
printf("%d\n", query(i, j));
}
return 0;
}
