#include<bits/stdc++.h>
#define IL inline
#define reg register
#define ll long long
#define N 1000100
#define M 55000000
IL int read()
{
	reg int x=0,f=0; reg char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}

int n,q,rk[N],irk[N];

struct Point
{
	int x,y,id;
	IL bool operator <(const Point &a){return x<a.x;}
}p[N],oldp[N];

IL int Abs(reg int x){return x<0?-x:x;}
IL ll dist(reg int i,reg int j){return (ll)Abs(p[i].x-p[j].x)+Abs(p[i].y-p[j].y);}

int m,tot;

struct Node
{
	int l,r; ll k;
	IL bool operator <(const Node &a)const{return k<a.k;}
}s[N],qwq[N];

IL void cmin(reg ll &x,reg ll y){x>y?x=y:0;}

int ls[M],rs[M],rt1[N],rt2[N],cnt;

struct Tree{int mn,pos;}tr[M];

IL Tree merge(const Tree &a,const Tree &b)
{
	if(a.mn<b.mn)return a;
	return b;
}

IL int clone(reg int &o)
{
	ls[++cnt]=ls[o],rs[cnt]=rs[o],tr[cnt]=tr[o];
	return o=cnt;
}

void modify(reg int &o,reg int p,reg int k,reg int l=1,reg int r=n)
{
	tr[clone(o)]=merge(tr[o],(Tree){k,p});
	if(l==r)return; reg int mid=l+r>>1;
	if(mid>=p)modify(ls[o],p,k,l,mid);
	else modify(rs[o],p,k,mid+1,r);
}

Tree query(reg int o,reg int L,reg int R,reg int l=1,reg int r=n)
{
	if(!o||L>r||l>R)return {2e9+10,0}; if(L<=l&&r<=R)return tr[o];
	reg int mid=l+r>>1; return merge(query(ls[o],L,R,l,mid),query(rs[o],L,R,mid+1,r));
}

struct info
{
	int x,l,r,mid,f; ll k;
	IL bool operator <(const info &a)const{return k>a.k;}
};

main()
{
	n=read(),q=read(),m=n>>1;
	for(reg int i=1;i<=n;++i)p[i]=oldp[i]={read(),read(),i};
	std::sort(p+1,p+1+n,[&](const Point &a,const Point &b){return a.y<b.y;});
	for(reg int i=1;i<=n;++i)rk[p[i].id]=i,irk[i]=p[i].id;
	std::sort(p+1,p+1+n),tr[0]={2e9+10,0};
	for(reg int i=1;i<=n;++i)
	{
		modify(rt1[i]=rt1[i-1],rk[p[i].id],-p[i].x-p[i].y);
		modify(rt2[i]=rt2[i-1],rk[p[i].id],-p[i].x+p[i].y);
	}
	std::priority_queue<info>Q;
	for(reg int i=2,j;i<=n;++i)
	{
		j=rk[p[i].id];
		Tree t=query(rt1[i-1],1,j);
		if(t.pos)Q.push({i,1,j,t.pos,1,(ll)p[i].x+p[i].y+t.mn});
		t=query(rt2[i-1],j,n);
		if(t.pos)Q.push({i,j,n,t.pos,2,(ll)p[i].x-p[i].y+t.mn});
	}
	for(reg int o=1,i,j,l,r;o<=m;++o)
	{
		info h=Q.top(); Q.pop(); Tree t;
		i=p[h.x].id,j=irk[h.mid];
		if(i>j)std::swap(i,j);
		qwq[o]={i,j,h.k},i=h.x;
		
		l=h.l,r=h.mid-1;
		if(h.f==1)
		{
			t=query(rt1[i-1],l,r);
			if(t.pos)Q.push({i,l,r,t.pos,1,(ll)p[i].x+p[i].y+t.mn});
		}else
		{
			t=query(rt2[i-1],l,r);
			if(t.pos)Q.push({i,l,r,t.pos,2,(ll)p[i].x-p[i].y+t.mn});			
		}
		
		l=h.mid+1,r=h.r;
		if(h.f==1)
		{
			t=query(rt1[i-1],l,r);
			if(t.pos)Q.push({i,l,r,t.pos,1,(ll)p[i].x+p[i].y+t.mn});
		}else
		{
			t=query(rt2[i-1],l,r);
			if(t.pos)Q.push({i,l,r,t.pos,2,(ll)p[i].x-p[i].y+t.mn});			
		}
	}
	for(reg int i=1;i<=n;++i)p[i]=oldp[i];
	tot=0;
	for(reg int i=1,j;i<=m;++i)
	{
		bool ok=1;
		for(j=1;j<=tot&&ok;++j)if(qwq[i].l<=s[j].l&&s[j].r<=qwq[i].r)ok=0;
		if(ok)s[++tot]=qwq[i];
	}
	for(reg int l,r,i,j;q--;)
	{
		l=read(),r=read();
		bool find=0;
		for(i=1;i<=tot&&!find;++i)if(l<=s[i].l&&s[i].r<=r)
			printf("%lld\n",s[i].k),find=1;
		if(find)continue;
		for(i=l;i<=r;++i)oldp[i]=p[i];
		std::sort(p+l,p+r+1); reg ll ans=1e18;
		for(i=l;i<=r;++i)for(j=i-1;j>=l&&j>=i-10;--j)
			cmin(ans,dist(i,j));
		printf("%lld\n",ans);
		for(i=l;i<=r;++i)p[i]=oldp[i];
	}
}

answer.code: In function ‘Tree query(int, int, int, int, int)’:
answer.code:62:36: error: narrowing conversion of ‘2.00000001e+9’ from ‘double’ to ‘int’ [-Wnarrowing]
   62 |         if(!o||L>r||l>R)return {2e9+10,0}; if(L<=l&&r<=R)return tr[o];
      |                                 ~~~^~~
answer.code: At global scope:
answer.code:72:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   72 | main()
      | ^~~~
answer.code: In function ‘int main()’:
answer.code:78:40: error: narrowing conversion of ‘2.00000001e+9’ from ‘double’ to ‘int’ [-Wnarrowing]
   78 |         std::sort(p+1,p+1+n),tr[0]={2e9+10,0};
      |                                     ~~~^~~