import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Math.abs;
import static java.lang.Math.min;

public class security {

    public static void main(String[] xxxx) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String NQline = reader.readLine();
            StringTokenizer tokenizer = new StringTokenizer(NQline);
            int N = Integer.parseInt(tokenizer.nextToken());
            int Q = Integer.parseInt(tokenizer.nextToken());

            Casino casino = new Casino(N);
            for (int i = 0; i < N; i++) {
                String guardCoords = reader.readLine();
                StringTokenizer guardCoordsTokens = new StringTokenizer(guardCoords);
                int x = Integer.parseInt(guardCoordsTokens.nextToken());
                int y = Integer.parseInt(guardCoordsTokens.nextToken());

                casino.placeGuard(x, y);
            }

            for (int i = 0; i < Q; i++) {
                String incidentCoords = reader.readLine();
                StringTokenizer incidentCoordsTokens = new StringTokenizer(incidentCoords);
                int x = Integer.parseInt(incidentCoordsTokens.nextToken());
                int y = Integer.parseInt(incidentCoordsTokens.nextToken());

                System.out.println(casino.searchNearestGuard(x, y));
            }
        }
    }

    private static class Casino {
        private static class Guard {
            int x;
            int y;

            Guard(int x, int y) {
                this.x = x;
                this.y = y;
            }

            int distanceTo(int x, int y) {
                int steps = 0;
                int xdiff = abs(this.x - x);
                int ydiff = abs(this.y - y);
                int min = min(xdiff, ydiff);

                steps += min;

                if (xdiff == ydiff) {
                    // nothing
                }  else if (xdiff == min) {
                    steps += ydiff - min;
                } else if (ydiff == min) {
                    steps += xdiff - min;
                }
                return steps;
            }
        }
        private List<Guard> casinaGuards;

        Casino(int nGuards) {
            this.casinaGuards = new ArrayList<>(nGuards);
        }

        public void placeGuard(int x, int y) {
            casinaGuards.add(new Guard(x, y));
        }

        public int searchNearestGuard(int x, int y) {
            int minDistance = Integer.MAX_VALUE;
            for (Guard g : casinaGuards) {
                int distance = g.distanceTo(x, y);
                if (distance < minDistance) {
                    minDistance = distance;
                }
            }
            return minDistance;
        }
    }
}