#include <iostream>
#include <cmath>
#include <map>

int getDistance(int x1, int y1, int x2, int y2) {
			int dx = std::abs(x1 - x2);
			int dy = std::abs(y1 - y2);

			int diagonal = std::min(dx, dy);
			return diagonal + dx - diagonal + dy - diagonal; 			
}

int main () {
	int n, q;
	std::cin >> n >> q;

	int guards[n][2];
	int incidents[q][2];

	//return 0;
	std::map<int, std::map<int, int> >matrix;
	//char matrix[5001][5001];

	for (int i = 0; i < 5001; i++) {
		matrix[i] = std::map<int, int>();
	}

	for (int i = 0; i < n; i++) {
		std::cin >> guards[i][0] >> guards[i][1];
		matrix[guards[i][0]][guards[i][1]] = 1;
	}
	for (int i = 0; i < q; i++) {
		std::cin >> incidents[i][0] >> incidents[i][1];
		/*int min = -1
		for (int j = 0; j < n; j++) {
			int dx = std::abs(incidents[i][0] - guards[j][0]);
			int dy = std::abs(incidents[i][1] - guards[j][1]);

			int diagonal = std::min(dx, dy);
			int curMin = diagonal + dx - diagonal + dy - diagonal; 
			if (curMin < min      || min == -1) {
				min = curMin;
			}
		}
		std::cout << min << "\n";*/
		int zone = 0;
		while (1) {
			int x1 = std::max(incidents[i][0] - zone, 0);
			int x2 = std::min(incidents[i][0] + zone, 5000);
			int y1 = std::max(incidents[i][1] - zone, 0);
			int y2 = std::min(incidents[i][1] + zone, 5000); 
			int min = -1;
			for (int x = x1; x <= x2; x++) {
if (matrix[x][y1]) {
				int distance = getDistance(x, y1, incidents[i][0], incidents[i][1]);
				if (distance < min || min == -1) {
					min = distance;
				}
}
if (matrix[x][y2]) {
				int distance = getDistance(x, y2, incidents[i][0], incidents[i][1]);
				if (distance < min || min == -1) {
					min = distance;
				}
}
			}
			for (int y = y1; y <= y2; y++) {
if (matrix[x1][y]) {
				int distance = getDistance(x1, y, incidents[i][0], incidents[i][1]);
				if (distance < min || min == -1) {
					min = distance;
				}
}
if (matrix[x2][y]) {
				int distance = getDistance(x2, y, incidents[i][0], incidents[i][1]);
				if (distance < min || min == -1) {
					min = distance;
				}
}
			}
			if (min != -1) {
				std::cout << min << "\n";
				break;
			}
			zone++;
		}
	}

	
}