import java.util.Scanner;

/**
 *
 * @author cteam010
 */
public class Security {
    
    
     public static void main(String[] args) {
            class Point{
               int x,y;
               Point(int x, int y){
                   this.x = x;
                   this.y= y;
               }

               double findDist(Point c){
                   int xx = Math.abs(x-c.x);
                   int yy = Math.abs(y-c.y);

                   int distD = xx*xx + yy*yy;
                   return Math.sqrt(distD);
               }

           }
         
        Scanner sc = new Scanner(System.in);
        int g,in;
        g = sc.nextInt();
        in = sc.nextInt();
        
        Point []guards = new Point[g];
        
        for(int i = 0; i < g; i++){
            guards[i] = new Point(sc.nextInt(), sc.nextInt());
        }
        for(int i = 0; i < in; i++){
            Point inc = new Point(sc.nextInt(), sc.nextInt());
            double min = Double.MAX_VALUE;
            for(int j = 0; j < g; j++){
                double some = inc.findDist(guards[j]);
                min = (min > some) ? some : min;
            }
            System.out.println((int)min);
        }
        
        for(int i = 0; i < in; i++){
            
        }
        
    }
}