import java.util.Scanner;


public class security {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int Nguards = scanner.nextInt();
        int Nincidents = scanner.nextInt();
        
        int[][] guards = new int[Nguards][2];
        
        for (int i = 0; i < Nguards; i++) {
            guards[i] = new int[]{scanner.nextInt(), scanner.nextInt()};
        }
        
        for (int i = 0; i < Nincidents; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            
            System.out.print(neareastGuard(guards, x, y) + "\r\n");
        }
        
    }
    
    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);
    }
    
}