import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Security {

    public final static int[] X = new int[]{1,1,1,0,-1,-1,-1,0};
    public final static int[] Y = new int[]{-1,0,1,1,1,0,-1,-1};

    public static boolean can(int x, int y, int[][] map, int maxX, int maxY) {
        if (x < 0 || y < 0 || x > maxX || y > maxY) {
            return false;
        }
        return map[x][y] == -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int GS;
        int QS;

        String[] d = br.readLine().split(" ");
        GS = Integer.parseInt(d[0]);
        QS = Integer.parseInt(d[1]);

        int[][] guards = new int[GS][2];

        int maxX = 5001;
        int maxY = 5001;

        for (int i = 0; i < GS; i++) {
            d = br.readLine().split(" ");
            guards[i][0] = Integer.parseInt(d[0]);
            guards[i][1] = Integer.parseInt(d[1]);

//            maxX = Math.max(maxX, guards[i][0]);
//            maxY = Math.max(maxY, guards[i][1]);

        }

        int[][] map = new int[maxX+1][];
        for (int i = 0; i <= maxX; i++) {
            map[i] = new int[maxY+1];
            Arrays.fill(map[i], -1);
        }

        Queue<int[]> que = new LinkedList<>();

        for (int i = 0; i < GS; i++) {
            que.add(new int[]{guards[i][0], guards[i][1], 0});
        }
        int counter = 0;
        while (que.size() > 0) {
            int[] acc = que.poll();
            int x = acc[0];
            int y = acc[1];

            map[x][y] = acc[2];

            for (int i = 0; i < 8; i++) {
                if (can(x+X[i], y+Y[i], map, maxX, maxY)) {
                    map[x+X[i]][y+Y[i]] = acc[2]+1;
                    que.add(new int[]{x+X[i], y+Y[i], acc[2]+1});
                }
            }
            counter++;
        }

        for (int i = 0; i < QS; i++) {
            d = br.readLine().split(" ");
            int x = Integer.parseInt(d[0]);
            int y = Integer.parseInt(d[1]);

//            int diffX = 0;
//            int diffY = 0;
//
//            if (x > maxX) {
//                diffX = x-maxX;
//                x = maxX;
//            }
//            if (y > maxY) {
//                diffY = y-maxY;
//                y = maxY;
//            }
//
//            int value = map[x][y];
//            if (diffX > 0 || diffY > 0) {
//                if ()
//            }

            System.out.println(map[x][y]);

        }

            br.close();
    }
}