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

using namespace std;

const int SIZE = 5001;
const int SQUARED = SIZE * SIZE;

vector<int> map(SQUARED, INT_MAX);

bool upgrade(int x, int y, int val) {
	if (x >= SIZE || y >= SIZE || x < 0 || y < 0)
		return false;
		
	if (map[x * SIZE + y] > val) {
		map[x * SIZE + y] = val;
		return true;
	}

	return false;
}

int main() {
	int guardCount, incidentCount;
	cin >> guardCount;
	cin >> incidentCount;

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

		
		bool upgraded;
		int dist = 0;
		do {
			upgraded = false;
			
			int tlX = x - dist;
			int tlY = y - dist;

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

			int length = dist*2 + 1;

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

				int rX = trX;
				int rY = trY + j;

				upgraded = upgrade(lX, lY, dist) || upgraded;
				upgraded = upgrade(rX, rY, dist) || upgraded;
			}

			for (int j = 1; j < length - 1; j++) {
				int tX = tlX + j;
				int tY = tlY;

				int bX = tlX + j;
				int bY = tlY + length - 1;

				upgraded = upgrade(tX, tY, dist) || upgraded;
				upgraded = upgrade(bX, bY, dist) || upgraded;
			}

		dist++;
		} while (upgraded == true);
	}

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

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

	return 0;
}