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

int min(int x, int y);
int max(int x, int y);

int main(){

	long int guards, inc;
	scanf("%ld %ld",&guards, &inc);
	
	long int pole_guards[guards][2];
	long int pole_inc[inc][2];
	
	long int pole_vysledok[inc][guards];
	long int pole_vysledok2[inc];
	
	long int i;
	for(i=0; i<guards; i++)
	{	scanf("%ld %ld",&pole_guards[i][0], &pole_guards[i][1]);
	}
	for(i=0; i<inc; i++)
	{	scanf("%ld %ld",&pole_inc[i][0], &pole_inc[i][1]);
	}
	
	long int j;
	
	for(i=0; i<inc; i++)
	{	for(j=0; j<guards; j++)
		{	int pom0,pom1;
			pom0=abs(pole_guards[j][0]-pole_inc[i][0]);
			pom1=abs(pole_guards[j][1]-pole_inc[i][1]);
			pole_vysledok[i][j]=max(pom0,pom1);
		}
	}
	
	for(i=0; i<inc; i++)
		{pole_vysledok2[i]=min(pole_vysledok[i][0],pole_vysledok[i][1]);
		printf("%ld\n",pole_vysledok2[i]);}

	
	return 0;
}

int min(int x, int y)
{	if (x<y)
		return x;
	else
		return y;
}

int max(int x, int y)
{	if (x>y)
		return x;
	else
		return y;
}