#include <vector>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <utility>
#include <deque>

using namespace std;

int SIZE_X = 0;
int SIZE_Y = 0;


bool upgrade(int x, int y, int val, vector<int>& map) {
	if (x >= SIZE_X || y >= SIZE_Y || x < 0 || y < 0)
		return false;
		

	if (map[y * SIZE_X + x] > val) {
		map[y * SIZE_X + x] = val;
		return true;
	}


	return false;
}

int countCoord(int x, int y){
	return SIZE_X * y + x;
}

bool isFree(int x, int y, vector<int>& map){
	if (x >= SIZE_X || y >= SIZE_Y || x < 0 || y < 0)
		return false;
	if (map[countCoord(x, y)] == INT_MAX)  
		return true;
	return false;
}

int main() {
	int guardCount, incidentCount;
	cin >> guardCount;
	cin >> incidentCount;
	vector<pair<int, int>> guards(guardCount);
	vector<pair<int, int>> incidents(incidentCount);
	

	for (int i = 0; i < guardCount; i++) {
		int x, y;
		cin >> x;
		cin >> y;

		if (SIZE_X < x + 1)
			SIZE_X = x + 1;

		if (SIZE_Y < y + 1)
			SIZE_Y = y + 1;

		guards[i] = make_pair(x, y);
	}

	for (int i = 0; i < incidentCount; i++) {
		int x, y;
		cin >> x;
		cin >> y;

		if (SIZE_X < x + 1)
			SIZE_X = x + 1;

		if (SIZE_Y < y + 1)
			SIZE_Y = y + 1;

		incidents[i] = make_pair(x, y);
	}


	deque<pair<int, int>> fronta;
	vector<int> map(SIZE_X * SIZE_Y, INT_MAX);






	for (int i = 0; i < guardCount; i++) {
		int x, y;
		x = guards[i].first;
		y = guards[i].second;

		fronta.push_back(make_pair(x, y));
		map[y * SIZE_X + x] = 0;

	}

	while (!fronta.empty()){
		pair<int, int> coords = fronta[0];
		fronta.pop_front();
		int x = coords.first;
		int y = coords.second;

		int newVal = map[countCoord(x, y)] + 1;
		
		
		
		int dist = 1;
		int tlX = x - dist;
		int tlY = y - dist;

		int trX = x + dist;
		int trY = tlY;
		int length = 3;


		for (int j = 0; j < length; j++) {
			int lX = tlX;
			int lY = tlY + j;
			if (isFree(lX, lY, map)){
				map[countCoord(lX, lY)] = newVal;
				fronta.push_back(make_pair(lX, lY));
			} else {
}

			lX = trX;
			lY = trY + j;
			if (isFree(lX, lY, map)){
				map[countCoord(lX, lY)] = newVal;
				fronta.push_back(make_pair(lX, lY));
			}
		}

		for (int j = 1; j < length - 1; j++) {
			int lX = tlX + j;
			int lY = tlY;

			if (isFree(lX, lY, map)){
				map[countCoord(lX, lY)] = newVal;
				fronta.push_back(make_pair(lX, lY));
			}

			lX = tlX + j;
			lY = tlY + length - 1;

			if (isFree(lX, lY, map)){
				map[countCoord(lX, lY)] = newVal;
				fronta.push_back(make_pair(lX, lY));
			}

		}
	}


	for (int i = 0; i < incidentCount; i++) {
		int x, y;
		x = incidents[i].first;
		y = incidents[i].second;

		cout << map[y * SIZE_X + x] << endl;
	}
				

	return 0;
}