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++) {
                if (Math.max(incidents[i].x, incidents[i].y) < Math.max(guards[guards.length/2].x, guards[guards.length/2].y)) {
                    for (int j = 0; j < guards.length/2; j++) {
                        int temp = Math.max(Math.abs(incidents[i].x - guards[j].x), Math.abs(incidents[i].y - guards[j].y));
                        if (temp < incidents[i].distance) {
                            incidents[i].distance = temp;
                        }
                    }
                }
                else {
                    for (int k = guards.length/2; k < guards.length; k++) {
                        int temp = Math.max(Math.abs(incidents[i].x - guards[k].x), Math.abs(incidents[i].y - guards[k].y));
                        if (temp < incidents[i].distance) {
                            incidents[i].distance = temp;
                        }
                    }
                }
            }

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


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

    }

}