import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class security {

    public static void main(String[] args) throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        line = scanner.readLine();
        String[] data = line.split(" ");
        int Nguards = Integer.valueOf(data[0]);
        int Nincidents = Integer.valueOf(data[1]);
        
        int[][] guards = new int[Nguards][2];
        
        for (int i = 0; i < Nguards; i++) {
            line = scanner.readLine();
            data = line.split(" ");
            guards[i] = new int[]{Integer.valueOf(data[0]), Integer.valueOf(data[1])};
        }
        
        OutputStreamWriter out = new OutputStreamWriter(System.out, "utf-8");
        
        for (int i = 0; i < Nincidents; i++) {
            line = scanner.readLine();
            data = line.split(" ");

            int x = Integer.valueOf(data[0]);
            int y = Integer.valueOf(data[1]);
        
            out.append(String.valueOf(neareastGuard(guards, x, y)) );
            out.append('\r');
            out.append('\n');
        }
        out.flush();
    }
    
    public static int neareastGuard(int[][] guards, int x, int y) {
        int nearestX = 0, nearestY = 0;
        double minDistance = Double.MAX_VALUE;
        for (int i = 0; i < guards.length; i++) {
            
            int distanceX = Math.abs( x - guards[i][0] );
            int distanceY = Math.abs( y - guards[i][1] );
            
            double distance = Math.sqrt( distanceX * distanceX + distanceY * distanceY );
            if(minDistance > distance) {
                minDistance = distance;
                nearestX = distanceX;
                nearestY = distanceY;
            }
        }
        
        return Math.max(nearestX, nearestY);
    }
    
}