#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <math.h>

using namespace std;

int main() {

	int Nguards;
	int Nincidents;

	scanf("%d %d", &Nguards, &Nincidents);

	int guards[300000][2];

	for (int i = 0; i < Nguards; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		guards[i][0] = x;
		guards[i][1] = y;
	}

	for (int i = 0; i < Nincidents; i++) {
		int x, y;
		scanf("%d %d", &x, &y);

		int nearestX = 0, nearestY = 0;

		double minDistance = 100000;
		for (int j = 0; j < Nguards; j++) {

			int distanceX = abs(x - guards[j][0]);
			int distanceY = abs(y - guards[j][1]);

			double distance = sqrt( distanceX * distanceX + distanceY * distanceY );
			if(minDistance > distance) {
				minDistance = distance;
				nearestX = distanceX;
				nearestY = distanceY;
			}
		}

		if (nearestX > nearestY) {
			cout << nearestX << endl;
		}
		else {
			cout << nearestY << endl;
		}
	}

	return 0;
}