import java.util.Scanner;

public class Security {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int Q = sc.nextInt();
		int qx, qy, pom, min;
		int dy, dx;
		
		int[][] security = new int[N][2];
		
		for (int i = 0; i < N; i++) {
			security[i][0] = sc.nextInt();
			security[i][1] = sc.nextInt();
		}
		
		for (int i = 0; i < Q; i++) {
			qx = sc.nextInt();
			qy = sc.nextInt();
			min = Integer.MAX_VALUE;
			
			for (int j = 0; j < N; j++) {
				dy = Math.abs(qy - security[j][1]);
				dx = Math.abs(qx - security[j][0]);
				
				int maxd = Math.max(dx, dy);
				
				
				pom = maxd;
				if (pom < min)
					min = pom;
			}
			System.out.println(min);
		}
	}
}