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_nx = 5001;
			int smallest_ny = 5001;
			
			for(int g = 0; g < guardCount; g++) {
				int nx = Math.abs(incidents[i].x - guards[g].x);
				int ny = Math.abs(incidents[i].y - guards[g].y);
				
				
				if((nx + ny) < (smallest_nx + smallest_ny)) {
					smallest_nx = nx;
					smallest_ny = ny;
				}
			}
			
			int distance = getDistance(smallest_nx, smallest_ny);
			System.out.println(distance);
		}
		
	}
	
	public static int getDistance(int n1, int n2) {
		int nx = n1 * n1;
		int ny = n2 * n2;
		return (int)Math.floor(Math.sqrt(nx + ny));
	}

}