#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=1e18;
const int maxn=1e6+10;
int n,q;
ll ans[maxn];
struct que{
	int l,r,id;
};
struct point{
	int x,y,id;
	bool operator < (const point tmp) const{
		return x<tmp.x;
	}
}p[maxn],tmp[maxn];
ll dis(point a,point b){
	return 1ll*abs(a.x-b.x)+1ll*abs(a.y-b.y);
}
pair<int,int> cal(int l,int r){
	int res1=0,res2=0,cnt=0;
	ll ans=inf;
	for(int i=l;i<=r;i++) tmp[++cnt]=p[i];
	sort(tmp+1,tmp+cnt+1);
	for(int i=1;i<=cnt;i++){
		for(int j=i+1;j<=i+20&&j<=cnt;j++){
			if(dis(tmp[i],tmp[j])<ans){
				ans=dis(tmp[i],tmp[j]);
				res1=tmp[i].id,res2=tmp[j].id;
			}
		}
	}
	if(res1>res2) swap(res1,res2);
	return {res1,res2};
}
void solve(int l,int r,vector<que> v){
	if(v.empty()) return;
	// cout<<l<<" "<<r<<":\n";
	pair<int,int> res=cal(l,r);
	vector<que> v1,v2;
	for(auto it:v){
		if(it.l<=res.first&&it.r>=res.second) ans[it.id]=dis(p[res.first],p[res.second]);
		else if(it.l>res.first) v2.push_back(it);
		else v1.push_back(it);
	}
	// cout<<res.first<<" "<<res.second<<"\n";
	solve(l,res.second-1,v1),solve(res.first+1,r,v2);
}
int main(){
	// freopen("geo3.in","r",stdin);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
	vector<que> v;
	for(int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		v.push_back({l,r,i});
	}
	solve(1,n,v);
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}