#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int guards_x[320000];
int inc_x[320000];
int guards_y[320000];
int inc_y[320000];

int main() {
	int N,Q;
	scanf("%d %d", &N, &Q);
	for(int i =0; i < N; i++){
		scanf("%d %d", &guards_x[i], &guards_y[i]);
	}
	for(int i =0; i < Q; i++){
		scanf("%d %d", &inc_x[i], &inc_y[i]);
	}
	
	for(int i = 0; i < Q; i++) {
		int steps = 100000; 
		for(int i1 = 0; i1 < N; i1++) {
			int temp = abs(guards_y[i1] - inc_y[i]) > abs(guards_x[i1] - inc_x[i]) ? abs(guards_y[i1] - inc_y[i]) : abs(guards_x[i1] - inc_x[i]);
			if(steps > temp) {
				steps = temp;
			}
		}
		printf("%d\n", steps);
	}

	return 0;
}