#include<iostream>
using namespace std;
int n, m, k, Q;
bool check[1001][1001];
long long dp[1001][1001];
int xx[4] = { -1,1,2,2 };
int yy[4] = { 2,2,1,-1 };
const long long mod = 1e9;
long long dynamic(int x, int y)
{
check[x][y] = true;
for (int i = 0; i < 4; i++)
{
int a = x + xx[i], b = y + yy[i];
if (((a >= 1 && a <= n) && (b >= 1 && b <= m)) && check[a][b])
dp[x][y] = ((dp[x][y] % mod) + (dp[a][b] % mod)) % mod;
else if (((a >= 1 && a <= n) && (b >= 1 && b <= m)))
dp[x][y] = ((dp[x][y] % mod) + (dynamic(a, b) % mod)) % mod;
}
return dp[x][y];
}
int main()
{
freopen("SOCACH.inp", "r", stdin);
freopen("SOCACH.out", "w", stdout);
cin >> n >> m >> k >> Q;
for (int i = 0; i < k; i++)
{
int x, y;
cin >> x >> y;
check[x][y] = true;
}
check[n][m] = true;
dp[n][m] = 1;
for (int i = 0; i < Q; i++)
{
int x, y;
cin >> x >> y;
if (check[x][y])
cout << dp[x][y] << endl;
else
cout << dynamic(x, y) << endl;
}
}
I2luY2x1ZGU8aW9zdHJlYW0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgbiwgbSwgaywgUTsKYm9vbCBjaGVja1sxMDAxXVsxMDAxXTsKbG9uZyBsb25nIGRwWzEwMDFdWzEwMDFdOwppbnQgeHhbNF0gPSB7IC0xLDEsMiwyIH07CmludCB5eVs0XSA9IHsgMiwyLDEsLTEgfTsKCmNvbnN0IGxvbmcgbG9uZyBtb2QgPSAxZTk7Cgpsb25nIGxvbmcgZHluYW1pYyhpbnQgeCwgaW50IHkpCnsKCWNoZWNrW3hdW3ldID0gdHJ1ZTsKCWZvciAoaW50IGkgPSAwOyBpIDwgNDsgaSsrKQoJewoJCWludCBhID0geCArIHh4W2ldLCBiID0geSArIHl5W2ldOwoKCQlpZiAoKChhID49IDEgJiYgYSA8PSBuKSAmJiAoYiA+PSAxICYmIGIgPD0gbSkpICYmIGNoZWNrW2FdW2JdKQoJCQlkcFt4XVt5XSA9ICgoZHBbeF1beV0gJSBtb2QpICsgKGRwW2FdW2JdICUgbW9kKSkgJSBtb2Q7CgkJZWxzZSBpZiAoKChhID49IDEgJiYgYSA8PSBuKSAmJiAoYiA+PSAxICYmIGIgPD0gbSkpKQoJCQlkcFt4XVt5XSA9ICgoZHBbeF1beV0gJSBtb2QpICsgKGR5bmFtaWMoYSwgYikgJSBtb2QpKSAlIG1vZDsKCX0KCXJldHVybiBkcFt4XVt5XTsKfQppbnQgbWFpbigpCnsKCWZyZW9wZW4oIlNPQ0FDSC5pbnAiLCAiciIsIHN0ZGluKTsKCWZyZW9wZW4oIlNPQ0FDSC5vdXQiLCAidyIsIHN0ZG91dCk7CgljaW4gPj4gbiA+PiBtID4+IGsgPj4gUTsKCWZvciAoaW50IGkgPSAwOyBpIDwgazsgaSsrKQoJewoJCWludCB4LCB5OwoJCWNpbiA+PiB4ID4+IHk7CgkJY2hlY2tbeF1beV0gPSB0cnVlOwoJfQoJY2hlY2tbbl1bbV0gPSB0cnVlOwoJZHBbbl1bbV0gPSAxOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBROyBpKyspCgl7CgkJaW50IHgsIHk7CgkJY2luID4+IHggPj4geTsKCQlpZiAoY2hlY2tbeF1beV0pCgkJCWNvdXQgPDwgZHBbeF1beV0gPDwgZW5kbDsKCQllbHNlCgkJCWNvdXQgPDwgZHluYW1pYyh4LCB5KSA8PCBlbmRsOwoJfQp9Cg==