import javafx.util.Pair;

import java.util.*;

public class Security {

    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int guardsCount = sc.nextInt();
            int incidentCount = sc.nextInt();
            Coords[] guards = new Coords[guardsCount];
            for (int i = 0;i<guardsCount;i++) {
                guards[i] = new Coords(sc.nextInt(),sc.nextInt());
            }
            for (int i = 0; i<incidentCount;i++) {
                int incidentX = sc.nextInt();
                int incidentY = sc.nextInt();
                int minDistance = Integer.MAX_VALUE;
                for (int j = 0; j<guardsCount;j++) {
                    int distToGuard = Integer.max(Math.abs(guards[j].getKey()-incidentX),Math.abs(guards[j].getValue()-incidentY));
                    minDistance = minDistance>distToGuard?distToGuard:minDistance;
                }
                System.out.println(minDistance);
            }
    }
    static class Coords {
        int x;
        int y;

        public int getKey() {
            return x;
        }

        public int getValue() {
            return y;
        }

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