#include <cstdio>

#define coord(x, y)  (y + (x*5000))
#define max(a, b)    ((a>b) ? a : b)
#define min(a, b)    ((a<b) ? a : b)

int *matrix;

int solve(int a, int b) {
	if (matrix[coord(a, b)]) return 0;
	for (int radius = 1; radius < 5000; radius++) {
		const int left = b - radius;
		const int right = b + radius;
		const int up = a - radius;
		const int down = a + radius;
		
		if (left >= 0)
			for (int x = max(0, up); x < min(4999, down); x++)
				if (matrix[coord(x, left)]) return radius;
		
		if (right < 5000)
			for (int x = max(0, up); x < min(4999, down); x++)
				if (matrix[coord(x, right)]) return radius;

		if (up >= 0)
			for (int y = max(0, left); y < min(4999, right); y++)
				if (matrix[coord(up, y)]) return radius;
		
		if (down < 5000)
			for (int y = max(0, left); y < min(4999, right); y++)
				if (matrix[coord(down, y)]) return radius;
	}
	
	return 5000;
}

int main() {
	int guards, incidents;
	
	int a,b;
	
	scanf("%i %i\n", &guards, &incidents);

	matrix = new int[5000*5000];
	
	for (int i = 0; i < guards; i++) {
		scanf("%i %i\n", &a, &b);
		matrix[coord(a,b)] = 1;
	}
	
	for(int i = 0; i < incidents; i++){
		scanf("%i %i\n", &a, &b);
		int result = solve(a,b);
		printf("%i\n", result);
	}
}