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

class Guard {
    public int x;
    public int y;

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

}

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

            for(int j = 0; j < countIncidents; j++) {
                for(int k = 0; k < countGuards; k++) {
                    int temp = Math.max(Math.abs(incidents[j].x - guards[k].x), Math.abs(incidents[j].y - guards[k].y));
                    if (temp < incidents[j].distance) {
                        incidents[j].distance = temp;
                    }
                }
            }

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


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

    }

}