#include <cstdio>
#include <climits>
#include <cstdint>
#include <cstring>

#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;
}
*/

uint32_t *matrix;

void add_guard(int a, int b) {
	matrix[coord(a,b)] = 0;
	bool do_left = true;
	bool do_up = true;
	bool do_right = true;
	bool do_down = true;
	for (uint32_t 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 (do_left && left >= 0) {
			bool done_left = true;
			for (int x = max(0, up); x <= min(5000, down); x++) {
				uint32_t *dist = &matrix[coord(x, left)];
				if (*dist > radius) {
					done_left = false;
					*dist = radius;
				}
			}
			do_left = !done_left;
		}
		
		if (do_right && right < 5001) {
			bool done_right = true;
			for (int x = max(0, up); x <= min(5000, down); x++) {
				uint32_t *dist = &matrix[coord(x, right)];
				if (*dist > radius) {
					done_right = false;
					*dist = radius;
				}
			}
			do_right = !done_right;
		}

		if (do_up && up >= 0) {
			bool done_up = true;
			for (int y = max(0, left); y <= min(5000, right); y++) {
				uint32_t *dist = &matrix[coord(up, y)];
				if (*dist > radius) {
					done_up = false;
					*dist = radius;
				}
			}
			do_up = !done_up;
		}
		
		if (do_down && down < 5001) {
			bool done_down = true;
			for (int y = max(0, left); y <= min(5000, right); y++) {
				uint32_t *dist = &matrix[coord(down, y)];
				if (*dist > radius) {
					done_down = false;
					*dist = radius;
				}
			}
			do_down = !done_down;
		}
	}
}


/*
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;
	
	matrix = new uint32_t[5001*5001];
	memset(matrix, -1, 4 * 500 * 5001);
	
	scanf("%i %i\n", &G, &I);
	
	for (int i = 0; i < G; i++) {
		scanf("%i %i\n", &a, &b);
		add_guard(a, b);
	}
	
	/*
	for (int a = 0; a < 20; a++) {
		for (int b = 0; b < 20; b++)
			printf("%2u ", matrix[coord(a, b)]);
		putchar('\n');
	}
	putchar('\n');
	*/
		
	for(int i = 0; i < I; i++){
		scanf("%i %i\n", &a, &b);
		uint32_t result = matrix[coord(a, b)];
		printf("%u\n", result);
	}
}