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

using namespace std;

struct s
{
	int x, y;
};

int p, maxX, maxY;
int pole[5001][5001];
queue<s> fronta;
vector<s> problemy;


void check(s start, int x, int y)
{
	if(x < 0 || y < 0 || x > maxX || y > maxY || x > 5000 || y > 5000)
		return;
	
	if(pole[x][y] >= 0)
		return;
		
	if(pole[x][y] == -2)
		p--;
		
	pole[x][y] = pole[start.x][start.y] + 1;
	s poz;
	poz.x = x;
	poz.y = y;
	fronta.push(poz);
}


int main()
{
	int pocetB, pocetP, x, y;
	
	cin >> pocetB;
	cin >> pocetP;
	
	maxX = maxY = 0;

	for(int i = 0; i < 5001; i++)
		for(int j = 0; j < 5001; j++)
			pole[i][j] = -1;

	for(int i = 0; i < pocetB; i++)
	{
		cin >> x;
		cin >> y;
		pole[x][y] = 0;
		s poz;
		poz.x = x;
		poz.y = y;
		fronta.push(poz);
		if(x > maxX)
			maxX = x;
		if(y > maxY)
			maxY = y;
	}
	
	
	p = pocetP;
	
	for (int i = 0; i < pocetP; i++)
	{
		cin >> x;
		cin >> y;
		if(pole[x][y] != 0)
		{
			pole[x][y] = -2;
		}
		else
		{
			p--;
		}
		s poz;
		poz.x = x;
		poz.y = y;
		problemy.push_back(poz);
		if(x > maxX)
			maxX = x;
		if(y > maxY)
			maxY = y;
	}
	
	
	while(p > 0)
	{
		s start = fronta.front();
		fronta.pop();
		
		check(start, start.x - 1, start.y - 1);
		check(start, start.x, start.y - 1);
		check(start, start.x + 1, start.y - 1);
		
		check(start, start.x - 1, start.y);
		check(start, start.x + 1, start.y);
		
		check(start, start.x - 1, start.y + 1);
		check(start, start.x, start.y + 1);
		check(start, start.x + 1, start.y + 1);
		
	}
	
	for(int i = 0; i < pocetP; i++)
		cout << pole[problemy[i].x][problemy[i].y] << endl; 
		
	
	
	
	
	return 0;
}