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

using namespace std;

vector<vector<short>> pole;
queue<pair<short,short>> fronta;

bool check(short vrchol_x, short vrchol_y, short soused_x, short soused_y, int & pocet_problemu)
{
	//if(soused_x < 0 || soused_y < 0)
	//	cout << "----------------" << endl;
	if(pole[soused_x][soused_y] == -2)
		pocet_problemu--;
	if(pole[soused_x][soused_y] < 0)
	{
		pole[soused_x][soused_y] = pole[vrchol_x][vrchol_y] + 1;
		//cout << soused_x << " " << soused_y << " -> " << vrchol_x << " " << vrchol_y << "(" << pole[vrchol_x][vrchol_y] << ")" << endl;
	} else
		return false;
		
	//cout << "000000" << endl;
		
	fronta.push(make_pair(soused_x,soused_y));
	return true;
}

bool kontrola(int number, int max_x)
{
	if(number < 0)
		return false;
	if(number > max_x)
		return false;
		
	return true;
}

int main()
{
int max_x, max_y;
int x, y, b, p;
max_x = 0;
max_y = 0;

vector<pair<short,short>> problem;

pole.resize(5011);
for(int i = 0; i < 5011; ++i)
{
	pole[i].assign(5011,-1);
}


scanf(" %d %d", &b, &p);

for(int i = 0; i < b ; i++)  // nacteni bodyguard
{
	scanf(" %d %d", &x, &y);
	fronta.push(make_pair(x,y));
	pole[x][y] = 0;
	if(max_x < x)
		max_x = x;
	if(max_y < y)
		max_y = y;
}

for(int i =0; i < p; i++) // nacteni problems
{
	scanf(" %d %d", &x, &y);
	problem.push_back(make_pair(x,y));
	pole[x][y] = -2;
	if(max_x < x)
		max_x = x;
	if(max_y < y)
		max_y = y;
}

short vrchol_x;
short vrchol_y;

int pocet_problemu = p;
while(pocet_problemu)
{
	//cout << pocet_problemu << endl;
	vrchol_x = fronta.front().first;
	vrchol_y = fronta.front().second;
	fronta.pop();
	
	short soused_x = vrchol_x; // vychozi
	short soused_y = vrchol_y; // vychozi
	
	soused_y--; // prohledame y dole y = -1
	if(kontrola(soused_y, max_y))
	{
		if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y))  // y = -1 x=0
			check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
		soused_x--;
		if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y = -1 x = -1
			check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
		soused_x++;
		soused_x++;
		if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y = -1; x = 1
			check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
	}
	else
		soused_x++;
	soused_y++; // dve okolni policka
	if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y = 0; x = 1
		check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
	soused_x--;
	soused_x--;
	if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y =0; x = -1
		check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
	soused_y++; // policka y nahore
	if(kontrola(soused_y, max_y))
	{
		if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y = 1, x = -1
			check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
		soused_x++;
		if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y = 1; x = 0
			check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);	
		soused_x++;
		if(kontrola(soused_x, max_x) && kontrola(soused_y, max_y)) // y = 1; x = 1
			check(vrchol_x, vrchol_y, soused_x, soused_y, pocet_problemu);
			
	
	
	}		
		

}

//cout << "_______" << endl;

for(int i = 0; i < p; i++)
{
	cout << pole[problem[i].first][problem[i].second] << endl;
}


	return 0;
}