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


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