#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
const int yyj=1e9,inf=2e9;
#define eb emplace_back
#define ll long long
int n,Q;
struct Point{int x,y,z;};
vector<Point>a,b;
ll ans[N];
inline ll dist(Point x,Point y){return (ll)abs(x.x-y.x)+abs(x.y-y.y);}
void solve(vector<Point>c,vector<Point>q)
{
	if(c.empty()||q.empty()) return ;
	ll ret=inf;
	int len=c.size(),u=0,v=0;
	for(int i=0;i<len;i++)
	{
		for(int j=i+1;j<min(len,i+30);j++)
		{
			ll dis=dist(c[i],c[j]);
			if(dis<ret)
			{
				ret=dis;
				u=c[i].z;v=c[j].z;
			}
		}
	}
	vector<Point>c1,c2;
	vector<Point>q1,q2;
	if(u>v) swap(u,v);
	for(Point i:c)
	{
		if(i.z<v) c1.eb(i);
		if(i.z>u) c2.eb(i);
	}
	for(Point i:q)
	{
		if(i.x<=u&&i.y>=v) ans[i.z]=ret;
		else if(i.y<v) q1.eb(i);
		else q2.eb(i);
	}
	solve(c1,q1);
	solve(c2,q2);
}
int main()
{
	 // freopen("geo3.in","r",stdin);
	 // freopen("out.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		a.eb((Point){x,y,i});
	}
	for(int i=1;i<=Q;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		b.eb((Point){x,y,i});
	}
	sort(a.begin(),a.end(),[&](Point x,Point y){return x.x==y.x?x.y<y.y:x.x<y.x;});
	solve(a,b);
	for(int i=1;i<=Q;i++)
		printf("%lld\n",ans[i]);
}