#include <stdio.h>
#include <stdlib.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; }
template<class T> T min(T a, T b){ return a<b?a:b; }
template<class T> T min(T a, T b, T c){ return min(min(a,b), min(b,c)); }
int poolId=0;
struct TREE{
	int v;
	struct TREE* l;
	struct TREE* r;
};
struct TREE* pool;
struct TREE* makeTree(int v){
    struct TREE* t=pool+(poolId++);
    t->l=NULL;
    t->r=NULL;
    t->v=v;
    return t;
}
void tins(struct TREE* t,int v){
	while (1){
	if (v<t->v){
		if (t->l==NULL){
			t->l=makeTree(v);
			return;
		}
		t=t->l;
	}
	else if (v>t->v){
		if (t->r==NULL){
			t->r=makeTree(v);
			return;
		}
		t=t->r;
	}
	else{
		return;
	}
}
}
int tfind(struct TREE *t,int v){
	while (1){
	if (v<t->v){
		if (t->l==NULL)
			return t->v;
		
		t=t->l;
	}
	else if (v>t->v){
		if (t->r==NULL)
			return t->v;
		
		t=t->r;
	}
	else{
		return t->v;
		}

}
}
int tfind2(struct TREE *t,int v){
        while (1){
	if (v>t->v){
                if (t->r==NULL)
                        return t->v;

                t=t->r;
        }
        else if (v<t->v){
                if (t->l==NULL)
                        return t->v;

                t=t->l;
        }

	else{
             	return t->v;
                }
}
}

int tfind3(struct TREE *t,int v, int* t1){
	int pv=-100000000;
        while (1){
        if (v>t->v){
                if (t->r==NULL){
			*t1=t->v;
                        return pv;
		}
		pv=t->v;
                t=t->r;
        }
	else if (v<t->v){
                if (t->l==NULL){
			*t1=t->v;
                        return pv;
		}
		pv=t->v;
                t=t->l;
        }

	else{ 
		*t1=t->v;
             	return t->v;
                }
}
}
int main(){
	int N, Q;
	int a,b;
//	int x[300001], y[300001];
	scanf("%d %d", &N, &Q);
	pool=(struct TREE*)malloc(sizeof(struct TREE)*(N*2+2));
	struct TREE* tx=makeTree(-10000000);
	struct TREE* ty=makeTree(-10000000);
	for(int i=0;i<N;i++){
		scanf("%d %d",&a,&b);
		tins(tx,a*10000+b);
		tins(ty,b*10000+a);
	}
	for(int i=0;i<Q;i++){
//		int minimum=0;
		scanf("%d %d", &a, &b);
               
		int t1;//=tfind(tx,a*10000+b);
		//int t2=tfind2(tx,a*10000+b);
		int t3=tfind3(tx,a*10000+b,&t1);
		int x1=t1/10000; int y1=t1%10000; /*int x2=t2/10000; int y2=t2%10000; */int x3=t3/10000; int y3=t3%10000;

                int _t1;//=tfind(ty,b*10000+a);
//                int _t2=tfind2(ty,b*10000+a);
		int _t3=tfind3(ty,b*10000+a,&_t1);

                int _x1=_t1%10000; int _y1=_t1/10000;/* int _x2=_t2%10000; int _y2=_t2/10000; */int _x3=_t3%10000; int _y3=_t3/10000;

                


                int _dst= min(max(abs(a-_x1), abs(b-_y1)), /*max(abs(a-_x2), abs(b-_y2))*/ max(abs(a-_x3), abs(b-_y3)));

		int dst= min(max(abs(a-x1), abs(b-y1)), /*max(abs(a-x2), abs(b-y2))*/ max(abs(a-x3), abs(b-y3)));

		/*int y11=abs(b*10000+a-tfind(ty,b*10000+a));
		int y12=abs(b*10000+a-tfind2(ty,b*10000+a));*/
		//int dst = min(min(x11,x12),min(y11,y12)) %10000;	
		printf("%d\n",  min( _dst, dst));
	}
}