#include <stdio.h>
#include <string.h>

#define MAX_N 20
#define MAX_NN 110

#define prim 666013

int n, m, k, N, l;

int mat[MAX_NN][MAX_NN], init[MAX_NN][MAX_NN], aux[MAX_NN][MAX_NN];

int A[MAX_N][MAX_N], use[MAX_N][MAX_N];

int Q[2][MAX_N * MAX_N];

int d[4] = {-1, 1, 0, 0};

int c[2][MAX_N][MAX_N]; //pentru t-uri mici

int go(int x1, int y1, int x2, int y2) {
	int st = 0, dr = 1;

	if (A[x1][y1] || A[x2][y2])
		return 0;

	memset(use, 0, sizeof(use));

	Q[0][1] = x1;
	Q[1][1] = y1;
	use[x1][y1] = 1;

	if (use[x2][y2]) //cazul in care x1 = x2 && y1 = y2
		return 1;

	while (st < dr) {
    	st++;

		for (int dir = 0; dir < 4; dir++) {
			int x = Q[0][st] + d[dir];
			int y = Q[1][st] + d[3 - dir];
	
			if (0 < x && x <= n && 0 < y && y <= m && use[x][y] == 0 && A[x][y] == 0) {
				use[x][y] = 1;

				Q[0][++dr] = x;
				Q[1][dr] = y;

				if (use[x2][y2])
					return 1;
			}
		}
	}
	
	return 0;
}

inline int get_pos(int x, int y) {
	return (x - 1) * m + y;
}

void mul_mat() {
	memset(aux, 0, sizeof(aux));

   	for (int i = 1; i <= N; i++)
   		for (int j = 1; j <= N; j++) 
   			for (int k = 1; k <= N; k++) {
				aux[i][j] = aux[i][j] + (1LL * mat[i][k] * mat[k][j]) % prim;
				while (aux[i][j] > prim) 
					aux[i][j] -= prim;
			}

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			mat[i][j] = aux[i][j];
}

void mul_init() {
	memset(aux, 0, sizeof(aux));

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) 
 			for (int k = 1; k <= N; k++) {
                aux[i][j] = aux[i][j] + (1LL * mat[i][k] * init[k][j]) % prim;
            	while (aux[i][j] > prim)
					aux[i][j] -= prim;
			}

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            mat[i][j] = aux[i][j];
}

void inm_mat(int p) {
	if (p == 1)
		return;

	inm_mat(p / 2);
    mul_mat();
	
	if (p % 2 == 1)
		mul_init();
}

int brut_algo(int x1, int y1, int x2, int y2, int t) {
	memset(c, 0, sizeof(c));
    c[0][x1][y1] = 1;

    if (A[x1][y1] || A[x2][y2])
        return 0;

	l = 0;

    for (int p = 1; p <= t; p++) {
		l = 1 ^ l;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (A[i][j] == 0) 
                    for (int dir = 0; dir < 4; dir++) {
                        int x = i + d[dir];
                        int y = j + d[3 - dir];

                        if (0 < x && x <= n && 0 < y && y <= m && A[x][y] == 0) 
                            c[l][i][j] = (c[l][i][j] + c[1 ^ l][x][y]) % prim;
                    }
            }

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				c[1 ^ l][i][j] = 0;
	}

    return c[l][x2][y2];
}

int solve(int x1, int y1, int x2, int y2, int t) {
	if (t <= 20000)
		return brut_algo(x1, y1, x2, y2, t);

	memset(mat, 0, sizeof(mat));
	memset(init, 0, sizeof(init));

	//construesc matricea
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) 
        	if (A[i][j] == 0)
	        	for (int k = 0; k < 4; k++) {
					int x = i + d[k];
					int y = j + d[3 - k];

					if (0 < x && x <= n && 0 < y && y <= m && A[x][y] == 0) {
                    	mat[get_pos(x, y)][get_pos(i, j)] = 1;
						init[get_pos(x, y)][get_pos(i, j)] = 1;
					}
				}

	N = n * m;

	inm_mat(t);

	return mat[get_pos(x1, y1)][get_pos(x2, y2)];
}

int main() {
    
    freopen("robotel.in", "r", stdin);
    freopen("robotel.out", "w", stdout);

    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= k; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        A[x][y] = 1;
    }

    int Q;
    scanf("%d", &Q);
    for (int i = 1; i <= Q; i++) {
        int x1, y1, x2, y2, t;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &t);

		if (go(x1, y1, x2, y2)) //verific daca pot ajunge din pozitia x1 y1 in pozitia x2 y2
	        printf("%d\n", solve(x1, y1, x2, y2, t));
		else
			printf("0\n");
    }

    return 0;
}

