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

int main() {
	int inc, grd;
	vector<Guard> grds;
	int min = 0;
	int tmp_x, tmp_y;
	scanf("%d %d", &grd, &inc);
	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);
	}
	return 0;
}