#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct coor{
		int x;
		int y;
};

int main(){
	int o_sz, b_sz;
	scanf("%d %d",&o_sz, &b_sz);
	struct coor orok[100000];
	struct coor esetek[100000];
	
	int i,a;
	for(i = 0; i < o_sz; i++){
				scanf("%d %d",&orok[i].x,&orok[i].y);
	}
	
	for(i = 0; i < b_sz; i++){
				scanf("%d %d",&esetek[i].x,&esetek[i].y);
	}
	
	int mind;
	int dist;
	for (i =0; i < b_sz; i++){
		mind = 1000000;
		for (a =0; a < o_sz; a++){
			if(fabs(orok[a].x - esetek[i].x)>= fabs(orok[a].y - esetek[i].y))
				dist = fabs(orok[a].x - esetek[i].x);
			else
				dist = fabs(orok[a].y - esetek[i].y);
				
			if (mind > dist)
				mind = dist;
			
		}
	printf("%d\n",mind);
		}
		
	return 0;
}