import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.rmi.server.ObjID;
import java.util.Arrays;

class Guard implements Comparable {
    public int x;
    public int y;

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

    @Override
    public int compareTo(Object o) {
        Guard guard = (Guard) o;
        int i = Math.max(this.y, this.x);
        int j = Math.max(guard.x, guard.y);

        if (i < j) {
            return -1;
        }
        else if ( i == j) {
            return 0;
        }
        else {
            return 1;
        }
    }
}

class Incident {
    public int x;
    public int y;
    public int distance;

    public Incident(int x, int y) {
        this.x = x;
        this.y = y;
        distance = Integer.MAX_VALUE;
    }
}

public class Security {
    private static BufferedReader reader;
    private static String[] lines;
    private static String line;
    private static Guard[] guards;
    private static Incident[] incidents;


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

        try {
            line = reader.readLine();
            lines = new String[2];
            lines = line.split(" ");

            int countGuards = Integer.parseInt(lines[0]);
            int countIncidents = Integer.parseInt(lines[1]);

            guards = new Guard[countGuards];
            incidents = new Incident[countIncidents];

            String line;

            for (int i = 0; i < countGuards; i++) {
                line = reader.readLine();
                String[] someLines = new String[2];
                someLines = line.split(" ");
                Guard guard = new Guard(Integer.parseInt(someLines[0]), Integer.parseInt(someLines[1]));
                guards[i] = guard;
            }
            for (int i = 0; i < countIncidents; i++) {
                line = reader.readLine();
                String[] someLines = new String[2];
                someLines = line.split(" ");
                Incident incident = new Incident(Integer.parseInt(someLines[0]), Integer.parseInt(someLines[1]));
                incidents[i] = incident;
            }

            Arrays.sort(guards);


            for (int i = 0; i < countIncidents; i++) {
                recursive(incidents[i]);
            }

            for(int l = 0; l < countIncidents; l++) {
                System.out.println(incidents[l].distance);
            }


        } catch (IOException ex){
            System.out.println("Input not found");
        }

    }

    public static void recursive(Incident incident) {

        if (Math.max(incident.x, incident.y) < Math.max(guards[guards.length/2].x, guards[guards.length/2].y)) {
           recursive(0, guards.length/2 - 1, incident);
        }
        else {
            recursive(guards.length/2, guards.length - 1, incident);
        }
    }

    public static void recursive(int firstIndex, int lastIndex, Incident incident) {
        int sub = lastIndex - firstIndex;
        int midIndex;

        if (sub == 1) {

            for(int k = firstIndex; k < lastIndex; k++) {
                int temp = Math.max(Math.abs(incident.x - guards[k].x), Math.abs(incident.y - guards[k].y));
                if (temp < incident.distance) {
                    incident.distance = temp;
                }
            }
            return;
        } else {
            midIndex = firstIndex + ((sub) / 2);
        }
        if (firstIndex >= lastIndex) {
            int temp = Math.max(Math.abs(incident.x - guards[firstIndex].x), Math.abs(incident.y - guards[firstIndex].y));
            incident.distance = temp;
            return;
        }

        else if (Math.max(incident.x, incident.y) < Math.max(guards[midIndex].x, guards[midIndex].y)) {
            recursive(firstIndex, midIndex, incident);
        }
        else {
            recursive(midIndex, lastIndex, incident);
        }
    }

}