#include<bits/stdc++.h>
using namespace std;

struct info
{
    int mx[4];//xmax,xmin,ymax,ymin
    int id[4];
    info operator+(const info &k)const
    {
        info ret;
        if(mx[0]<k.mx[0])
        {
            ret.mx[0]=k.mx[0];
            ret.id[0]=k.id[0];
        }
        else
        {
            ret.mx[0]=mx[0];
            ret.id[0]=id[0];
        }
        if(mx[1]>k.mx[1])
        {
            ret.mx[1]=k.mx[1];
            ret.id[1]=k.id[1];
        }
        else
        {
            ret.mx[1]=mx[1];
            ret.id[1]=id[1];
        }
        if(mx[2]<k.mx[2])
        {
            ret.mx[2]=k.mx[2];
            ret.id[2]=k.id[2];
        }
        else
        {
            ret.mx[2]=mx[2];
            ret.id[2]=id[2];
        }
        if(mx[3]>k.mx[3])
        {
            ret.mx[3]=k.mx[3];
            ret.id[3]=k.id[3];
        }
        else
        {
            ret.mx[3]=mx[3];
            ret.id[3]=id[3];
        }
        return ret;
    }
};
const int N=233333;
const int inf=0x7f7f7f7f;
info seg[N+5];
int lson[N+5],rson[N+5];
int root,top;
int x[N+5],y[N+5];
int build(int l,int r)
{
    int ret=++top;
    if(l<r)
    {
        int mid=(l+r)/2;
        ret[lson]=build(l,mid);
        ret[rson]=build(mid+1,r);
        ret[seg]=ret[lson][seg]+ret[rson][seg];
    }
    else
    {
        ret[seg].mx[0]=ret[seg].mx[1]=x[l];
        ret[seg].mx[2]=ret[seg].mx[3]=y[l];
        ret[seg].id[0]=ret[seg].id[1]=ret[seg].id[2]=ret[seg].id[3]=l;
    }
    return ret;
}
info query(int cur,int l,int r,int ql,int qr)
{
    if(l==ql and r==qr)
    {
        return cur[seg];
    }
    int mid=(l+r)/2;
    if(qr<=mid)return query(cur[lson],l,mid,ql,qr);
    else if(ql>=mid+1)return query(cur[rson],mid+1,r,ql,qr);
    else return query(cur[lson],l,mid,ql,mid)+query(cur[rson],mid+1,r,mid+1,qr);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    root=build(1,n);
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        int tans=inf;
        auto u=query(root,1,n,l,r);
        for(int j=0;j<4;j++)
        {
            int pos=u.id[j];
            info ans;
            ans.mx[0]=ans.mx[2]=-inf;
            ans.mx[1]=ans.mx[3]=inf;
            if(l<pos)
                ans=ans+query(root,1,n,l,pos-1);
            if(pos<r)
                ans=ans+query(root,1,n,pos+1,r);
            tans=min(tans,max(ans.mx[0]-ans.mx[1],ans.mx[2]-ans.mx[3]));
        }
        cout<<tans<<"\n";
    }
    
    return 0;
}