#include <cstdio>
#include <climits>

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

static int abs(int n) {
	if (n < 0)
		return -n;
	else
		return n;
}


typedef struct {
	int a;
	int b;
} guard;

guard *guards;
int I, G;

/*
int solve(int a, int b) {
	if (matrix[coord(a, b)]) return 0;
	for (int radius = 1; radius < 5001; 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(5000, down); x++)
				if (matrix[coord(x, left)]) return radius;
		
		if (right < 5001)
			for (int x = max(0, up); x < min(5000, down); x++)
				if (matrix[coord(x, right)]) return radius;

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

static int solve(int a, int b) {
	int result = INT_MAX;
	for (int g = 0; g < G; g++) {
		const int adist = abs(guards[g].a - a);
		const int bdist = abs(guards[g].b - b);
		const int dist = max(adist, bdist);
		result = min(result, dist);
	}
	return result;
}

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

	guards = new guard[G];
	
	for (int i = 0; i < G; i++) {
		scanf("%i %i\n", &a, &b);
		guards[i].a = a;
		guards[i].b = b;
	}
	
	for(int i = 0; i < I; i++){
		scanf("%i %i\n", &a, &b);
		int result = solve(a,b);
		printf("%i\n", result);
	}
}