import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;


public class Security {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tokens;
		
		tokens = br.readLine().split(" ");
		int guardCount = Integer.parseInt(tokens[0]);
		int incidentsCount = Integer.parseInt(tokens[1]);
		
		Point[] guards = new Point[guardCount];
		Point[] incidents = new Point[incidentsCount];
		
		for(int i = 0; i < guardCount; i++) {
			tokens = br.readLine().split(" ");
			guards[i] = new Point(Integer.parseInt(tokens[0]), Integer.parseInt(tokens[1]));
		}
		
		for(int i = 0; i < incidentsCount; i++) {
			tokens = br.readLine().split(" ");
			incidents[i] = new Point(Integer.parseInt(tokens[0]), Integer.parseInt(tokens[1]));
		}
		
		for(int i = 0; i < incidentsCount; i++) {
			int smallest = Integer.MAX_VALUE;
			
			for(int g = 0; g < guardCount; g++) {
				int distance = getDistance(incidents[i], guards[g]);
				
				if(distance < smallest) {
					smallest = distance;
				}
			}
			
			System.out.println(smallest);
		}
		
	}
	
	public static int getDistance(Point p1, Point p2) {
		int nx = Math.abs(p1.x - p2.x) * Math.abs(p1.x - p2.x);
		int ny = Math.abs(p1.y - p2.y) * Math.abs(p1.y - p2.y);
		return (int)Math.floor(Math.sqrt(nx + ny));
	}

}