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[5000][5000];
		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;
		}
		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 {
				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 < 5000 && yrad < 5000 && pole[xrad][yrad] == 1) {
							output = vzdalenost;
							found = true;
							// System.out.println(found);
							break;
						}
						xrad--;
					}
					while (yrad > y - vzdalenost && !found) {
						// System.out.println("2 "+xrad +" " + yrad);
						if (xrad >= 0 && yrad >= 0 && xrad < 5000 && yrad < 5000 && 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 < 5000 && yrad < 5000 && 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 < 5000 && yrad < 5000 && 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);
				}
			}
		}
	}
}