#include <stdio.h>

/*
	x[i] ... *(x+i)
	*x == x[0] == *(x+0)
*/

template<class T> T abs(T v){ return v>0?v:-v; }
template<class T> T max(T a, T b){ return a>b?a:b; }
int main(){
	int N, Q;
	int x[300001], y[300001];
	scanf("%d %d", &N, &Q);
	for(int i=0;i<N;i++){
		scanf("%d %d", x+i, y+i);
	}
	for(int i=0;i<Q;i++){
		int minimum=0;
		int a,b; scanf("%d %d", &a, &b); int dst=0;
		for(int j=0;j<N;j++){
			int dst = max(abs(a - x[j]), abs(b - y[j]));
			if(j==0 || dst<minimum)
				minimum=dst;
		}
		printf("%d\n", minimum);
	}
}