#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class Guard {
public:
	int x;
	int y;
	Guard(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

int get_distance(int x, int y, Guard g) {
	int dist_x = abs(x - g.x);
	int dist_y = abs(y - g.y);
	return dist_x > dist_y ? dist_x : dist_y;
}

vector<vector<bool>> pole;


int detector(int x, int y) {
	int step = 0;

	if(pole[x][y])
		return 0;
	while(true)
	{
//lad;
		for(int xs = x - step; xs <= x + step; xs++)
		{
//lad;
			if (xs>=0 && xs<= 5000 && y-step <= 5000 && y-step >=0) {
				if(pole[xs][y-step])
				return step;
			}

			if (xs>=0 && xs<= 5000 && y + step <= 5000 && y + step >=0) {
				if(pole[xs][y+step])
					return step;
			}
			
		}

		for(int ys = y-step; ys <= y+step; ys++)
		{
//lad;
			if (ys >= 0 && ys <= 5000 && x-step <= 5000 && x-step >= 0) {
				if(pole[x-step][ys])
					return step;
			}
			if (ys >= 0 && ys <= 5000 && x + step <= 5000 && x + step >= 0) {
				if(pole[x+step][ys])
					return step;
			}
		}
		step++;
	}
}

int main() {
	int inc, grd;
	vector<Guard> grds;
	int min = 0;
	int tmp_x, tmp_y;
	scanf("%d %d", &grd, &inc);
	if (grd < 1000) {
		for (int i = 0 ; i < grd ; i++) {
			scanf("%d %d", &tmp_x, &tmp_y);
			grds.push_back(Guard(tmp_x, tmp_y));
		}

		int size = grds.size();
		int dist;
		for (int i = 0 ; i < inc ; i++) {
			scanf("%d %d", &tmp_x, &tmp_y);

			min = get_distance(tmp_x, tmp_y, grds[0]);

			for (int j = 0 ; j < size ; j++) {
				if ((dist = get_distance(tmp_x, tmp_y, grds[j])) < min) {
					min = dist;
				}
			}
			printf("%d\n", min);
		}
	}
	else {

		for(int i = 0;i<=5000;i++)
		{
			pole.push_back(vector<bool> (5001, false));
		}


		int x, y;
		for (int i = 0 ; i < grd ; i++) {
//lad;		
		scanf("%d %d", &x, &y);
			pole[x][y] = true;
		}
		for (int i = 0 ; i < inc ; i++) {
//lad;		
		scanf("%d %d", &x, &y);
			printf("%d\n", detector(x,y));
		}
	}
	return 0;
}