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