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

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);
            }

            casino.sortGuards();

            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 implements Comparable<Guard> {
            int x;
            int y;

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

            int distanceTo(Coordinate c) {
                int steps = 0;
                int xdiff = abs(this.x - c.x);
                int ydiff = abs(this.y - c.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;
            }

            @Override
            public int compareTo(Guard o) {
                return this.x - o.x;
            }
        }

        private static class Coordinate {
            int x;
            int y;
            int minDistance = Integer.MAX_VALUE;

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

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;

                Coordinate that = (Coordinate) o;

                if (x != that.x) return false;
                return y == that.y;
            }

            @Override
            public int hashCode() {
                int result = x;
                result = 31 * result + y;
                return result;
            }
        }
        private List<Guard> casinaGuards;
        private HashMap<Coordinate, Integer> memoizationCache = new HashMap<>();

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

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

        public void sortGuards() {
            Collections.sort(casinaGuards);
        }

        public int searchNearestGuard(int x, int y) {
            Integer minDistance = memoizationCache.computeIfAbsent(new Coordinate(x, y), coordinate -> {
                int prevDistance = Integer.MAX_VALUE;
                for (Guard g : casinaGuards) {
                    int distanceBetweenGuardAndIncident = g.distanceTo(coordinate);
                    if (distanceBetweenGuardAndIncident < coordinate.minDistance) {
                        coordinate.minDistance = distanceBetweenGuardAndIncident;
                    }

                    if (prevDistance < distanceBetweenGuardAndIncident) {
                        return coordinate.minDistance;
                    }

                    prevDistance = distanceBetweenGuardAndIncident;
                }
                return coordinate.minDistance;
            });

            return minDistance;
        }
    }
}