#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,inf=~0U>>1;
struct Point
{
    int x,y,id;
}P[maxn];
bool cmpx(const Point &a,const Point &b) {if (a.x!=b.x) return a.x<b.x;return a.y<b.y;}
bool cmpy(const Point &a,const Point &b) {if (a.y!=b.y) return a.y<b.y;return a.x<b.x;}
struct Segment_Tree
{
    #define ls (o<<1)
    #define rs ((o<<1)|1)
    #define mid ((l+r)>>1)
    struct Info
    {
        Point maxx,max2x,minx,min2x;
        Point maxy,max2y,miny,min2y;
    }I[maxn<<2];
    int n;
    void Update(Info &o,Info &l,Info &r)
    {
    	Point tmp[5];
    	tmp[0]=l.maxx;tmp[1]=l.max2x;tmp[2]=r.maxx;tmp[3]=r.max2x;
    	sort(tmp,tmp+4,cmpx);
    	o.maxx=tmp[3];o.max2x=tmp[2];
    	tmp[0]=l.minx,tmp[1]=l.min2x,tmp[2]=r.minx,tmp[3]=r.min2x;
    	sort(tmp,tmp+4,cmpx);
    	o.minx=tmp[0];o.min2x=tmp[1];
    	tmp[0]=l.maxy;tmp[1]=l.max2y;tmp[2]=r.maxy;tmp[3]=r.max2y;
    	sort(tmp,tmp+4,cmpy);
    	o.maxy=tmp[3];o.max2y=tmp[2];
    	tmp[0]=l.miny,tmp[1]=l.min2y,tmp[2]=r.miny,tmp[3]=r.min2y;
    	sort(tmp,tmp+4,cmpy);
    	o.miny=tmp[0];o.min2y=tmp[1];
    }
    void Update(int o)
    {
    	Update(I[o],I[ls],I[rs]);
    }
    void Build(int o,int l,int r)
    {
    	if (l==r)
		{
			I[o].maxx=I[o].maxy=I[o].minx=I[o].miny=P[l];
			I[o].max2x=I[o].max2y=P[0],I[o].min2x=I[o].min2y=P[n+1];
			return;
		}
		Build(ls,l,mid);
		Build(rs,mid+1,r);
		I[o].maxx=I[o].max2x=I[o].maxy=I[o].max2y=P[0];
		I[o].minx=I[o].min2x=I[o].miny=I[o].min2y=P[n+1];
		Update(o);
    }
    void Build(int _n)
    {
    	n=_n;
    	Build(1,1,n);
    }
    void Query(int o,int l,int r,int a,int b,Info &res)
    {
    	if (a<=l && r<=b)
    	{
    		Update(res,res,I[o]);
    		return;
    	}
    	if (a<=mid) Query(ls,l,mid,a,b,res);
    	if (b> mid) Query(rs,mid+1,r,a,b,res);
    }
    void Fix(Info &x,int id)
    {
    	if (x.maxx.id==id) x.maxx=x.max2x;
    	if (x.maxy.id==id) x.maxy=x.max2y;
    	if (x.minx.id==id) x.minx=x.min2x;
    	if (x.miny.id==id) x.miny=x.min2y;
    }
	int Query(int l,int r)
	{
		if (r==l) return 0;
		Info res,tmp;
		res.maxx=res.max2x=res.maxy=res.max2y=P[0];
		res.minx=res.min2x=res.miny=res.min2y=P[n+1];
		Query(1,1,n,l,r,res);
		int id,ans=inf;
		tmp=res;id=res.maxx.id;
		Fix(tmp,id);ans=min(ans,max(tmp.maxx.x-tmp.minx.x,tmp.maxy.y-tmp.miny.y));
		tmp=res;id=res.maxy.id;
		Fix(tmp,id);ans=min(ans,max(tmp.maxx.x-tmp.minx.x,tmp.maxy.y-tmp.miny.y));
		tmp=res;id=res.minx.id;
		Fix(tmp,id);ans=min(ans,max(tmp.maxx.x-tmp.minx.x,tmp.maxy.y-tmp.miny.y));
		tmp=res;id=res.miny.id;
		Fix(tmp,id);ans=min(ans,max(tmp.maxx.x-tmp.minx.x,tmp.maxy.y-tmp.miny.y));
		return ans;
	}
}T;
int n,q;
int main()
{
	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;
	P[0].x=P[0].y=-inf;P[0].id=0;
	P[n+1].x=P[n+1].y=inf;P[n+1].id=n+1;
	T.Build(n);
	while (q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",T.Query(l,r));
	}
	return 0;
}