#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <iostream>

#define rep(i, j) for(int i = 0; i < j; ++i)
#define ii pair<int,int>

using namespace std;

vector<queue<ii>> q;

int steps[5100][5100];
int unvisited;

bool isIn(int x, int y) {
    if(x>=0 && x<5001 && y>=0 && y<5001) 
	return true;
else return false;
}

void bfs(int i, int dist) {
	while(steps[q[i].front().first][q[i].front().second]==dist) {
	ii pos = q[i].front(); q[i].pop();
	int x=pos.first;
	int y=pos.second;

	if(isIn(x,y+1) && dist+1<steps[x][y+1])
		{
			unvisited--; steps[x][y+1] = dist+1;
			q[i].push({x,y+1});
		}
	if(isIn(x,y-1) && dist+1<steps[x][y-1])
		{
			unvisited--; steps[x][y-1] = dist+1;
			q[i].push({x,y-1});
		}
	if(isIn(x+1,y) && dist+1<steps[x+1][y])
		{
			unvisited--; steps[x+1][y] = dist+1;
			q[i].push({x+1,y});
		}
	if(isIn(x-1,y) && dist+1<steps[x-1][y])
		{
			unvisited--; steps[x-1][y] = dist+1;
			q[i].push({x-1,y});
		}
	//cout<<unvisited<<endl;

	}
}

//typedef long long ll




int main(void){
	for(int i=0; i<5100; i++) 
		for(int j=0; j<5100; j++)
			steps[i][j]=1e9;

	int n,guards; cin>>n>>guards;

	q.resize(n);
	for(int i=0; i<n; i++) {
		int x,y;
		cin>>x>>y;
		q[i].push({x,y});
		steps[x][y] = 0;
	}
	unvisited=5001*5001;
	int dist=0;
	while(unvisited>0) {
		for(int i=0; i<n; i++)
			bfs(i,dist);
		dist++;
	}
	
	////
	for(int i=0; i<guards; i++) { int x,y; cin>>x>>y; cout<<steps[x][y]<<endl;}

	
	return 0;
}