#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define REP(A,B) for(int (A)=0;(A)<(B);(A)++)

int tab[5111][5111];

int main() {
	int n,qq;
	scanf("%d%d", &n, &qq);
	queue< pair<int, int> > Q;
	memset(tab, -1, sizeof(tab));
	REP(i, n) {
		int x,y;
		scanf("%d%d", &x, &y);
		tab[x][y] = 0;
		Q.push(mp(x, y));
	}
	while(!Q.empty()) {
		auto x = Q.front();
	//	printf("%d %d\n", x.first, x.second);
		Q.pop();
		for(int a = -1; a <= 1; a++) {
			for(int b = -1; b <= 1; b++) {
				if(a||b) {
					int nr = x.first+a, nc = x.second+b;
					if(nr >= 0 && nc >= 0 && nr <= 5000 && nc <= 5000) {
						int nval = tab[x.first][x.second]+1;
						if(tab[nr][nc] == -1) {
							tab[nr][nc] = nval;
							Q.push(mp(nr, nc));
						}
					}
				}
			}
		}
	}
	for(int i = 0; i < qq; i++) {
		int x,y;
		scanf("%d%d", &x, &y);
		printf("%d\n", tab[x][y]);
	}


	
	return 0;

}