import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Security {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line1 = br.readLine();
		int strazny = Integer.parseInt(line1.split(" ")[0]);
		int incident = Integer.parseInt(line1.split(" ")[1]);
		int[][] pole = new int[5001][5001];
		int[][] index = new int[strazny][2];
		for (int i = 0; i < (strazny); i++) {
			String line2 = br.readLine();
			int x = Integer.parseInt(line2.split(" ")[0]);
			int y = Integer.parseInt(line2.split(" ")[1]);
			pole[x][y] = 1;
			index[i][0] = x;
			index[i][1] = y;
		}
		for (int i = 0; i < incident; i++) {
			int output = 0;
			String line2 = br.readLine();
			int x = Integer.parseInt(line2.split(" ")[0]);
			int y = Integer.parseInt(line2.split(" ")[1]);
			int vzdalenost = 1;
			if (pole[x][y] == 1) {
				output = 0;
				System.out.println(output);
			} else {
				double minLength = Integer.MAX_VALUE;
				int minLengthIndex = 0;
				for (int j = 0; j < strazny; j++) {
					double pythagor = Math
							.sqrt((x - index[j][0]) * (x - index[j][0]) + (y - index[j][1]) * (y - index[j][1]));
					if (pythagor < minLength) {
						minLength = pythagor;
						minLengthIndex = j;
					}
				}
				if (Math.abs(index[minLengthIndex][0] - x) > Math.abs(index[minLengthIndex][1] - y))
					vzdalenost = Math.abs(index[minLengthIndex][0] - x);
				else
					vzdalenost = Math.abs(index[minLengthIndex][1] - y);

				System.out.println(vzdalenost);

//				minLength = minLength / Math.sqrt(2);
//				vzdalenost = (int) minLength;
//				boolean found = false;
//				while (true) {
//					int xrad = x + vzdalenost;
//					int yrad = y + vzdalenost;

//					while (xrad > x - vzdalenost) {
//						// System.out.println("x=" + xrad + " " + "y" + yrad);
//						if (xrad >= 0 && yrad >= 0 && xrad < 5001 && yrad < 5001 && pole[xrad][yrad] == 1) {
//							output = vzdalenost;
//							found = true;
//							break;
//						}
//						xrad--;
//					}
//					while (yrad > y - vzdalenost && !found) {
//						// System.out.println("2 "+xrad +" " + yrad);
//						if (xrad >= 0 && yrad >= 0 && xrad < 5001 && yrad < 5001 && pole[xrad][yrad] == 1) {
//							output = vzdalenost;
//							found = true;
//							break;
//						}
//						yrad--;
//
//					}
//					while (xrad < x + vzdalenost && !found) {
//						// System.out.println("3 "+xrad +" " + yrad);
//						if (xrad >= 0 && yrad >= 0 && xrad < 5001 && yrad < 5001 && pole[xrad][yrad] == 1) {
//							output = vzdalenost;
//							found = true;
//							break;
//						}
//						xrad++;
//
//					}
//					while (yrad < y + vzdalenost && !found) {
//						// System.out.println("4 "+xrad +" " + yrad);
//						if (xrad >= 0 && yrad >= 0 && xrad < 5001 && yrad < 5001 && pole[xrad][yrad] == 1) {
//							output = vzdalenost;
//							found = true;
//							break;
//						}
//						yrad++;
//
//					}
				// System.out.println(found);
//					if (found == true) {
//						System.out.println(output);
//						break;
//					}
//					vzdalenost++;
				// System.out.println(vzdalenost);

			}
		}
	}
}