#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 5005;
int d[maxn][maxn];
queue<pii> q;
int A[] = {0,0,1,1,1,-1,-1,-1}, B[] = {1,-1,1,0,-1,0,-1,1};
bool stop(pii h){
	if(min(h.fi, h.se) < 0 or max(h.fi, h.se) > 5000) return true;
	return d[h.fi][h.se];
}


void solve() {
	int n, t;
	scanf("%d %d", &n, &t);
	for(int i = 1; i <= n; i ++){
		int x, y;
		scanf("%d %d", &x, &y);
		if(d[x][y]) continue;
		d[x][y] = 1;
		q.push(mp(x,y));
	}
	while(q.size()){
		auto g = q.front();
		q.pop();
		for(int i = 0; i < 8; i ++){
			auto h = mp(g.fi+A[i], g.se+B[i]);
			if(stop(h)) continue;
			d[h.fi][h.se] = d[g.fi][g.se] + 1;
			q.push(h);
		}
	}
	while(t --){
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", d[x][y]-1);
	}
}

int main(){
solve();
return 0;
}