#include <bits/stdc++.h>

using namespace std;

const int INF=2000000000;

int n,q;
int X[100010],Y[100010];
set<pair<pair<int,int>,int> >s;
struct seg{
    int l,r,min,max,min2,max2;
}seg[2][400010];

inline void build(int pp,int p,int l,int r){
    seg[pp][p].l=l;seg[pp][p].r=r;
    if(l==r){
        seg[pp][p].min=seg[pp][p].max=pp==0?X[l]:Y[l];
        seg[pp][p].min2=INF;
        seg[pp][p].max2=-INF;
        return;
    }

    int mid=(l+r)>>1;
    build(pp,p<<1,l,mid);
    build(pp,p<<1|1,mid+1,r);

    seg[pp][p].min=min(seg[pp][p<<1].min,seg[pp][p<<1|1].min);
    seg[pp][p].max=max(seg[pp][p<<1].max,seg[pp][p<<1|1].max);
    seg[pp][p].min2=seg[pp][p<<1].min<seg[pp][p<<1|1].min?min(seg[pp][p<<1].min2,seg[pp][p<<1|1].min):min(seg[pp][p<<1].min,seg[pp][p<<1|1].min2);
    seg[pp][p].max2=seg[pp][p<<1].max>seg[pp][p<<1|1].max?max(seg[pp][p<<1].max2,seg[pp][p<<1|1].max):max(seg[pp][p<<1].max,seg[pp][p<<1|1].max2);
}

inline pair<int,int> queryMin(int pp,int p,int l, int r){
    if(l<=seg[pp][p].l&&seg[pp][p].r<=r)
        return make_pair(seg[pp][p].min,seg[pp][p].min2);

    int mid=(seg[pp][p].l+seg[pp][p].r)>>1;
    if(r<=mid)
        return queryMin(pp,p<<1,l,r);
    else
        if(l>mid)
            return queryMin(pp,p<<1|1,l,r);
        else{
            int temp[4];
            pair<int,int>temp1=queryMin(pp,p<<1,l,mid);
            temp[0]=temp1.first;
            temp[1]=temp1.second;
            temp1=queryMin(pp,p<<1|1,mid+1,r);
            temp[2]=temp1.first;
            temp[3]=temp1.second;
            sort(temp,temp+4);
            return make_pair(temp[0],temp[1]);
        }
}
inline pair<int,int> queryMax(int pp,int p,int l, int r){
    if(l<=seg[pp][p].l&&seg[pp][p].r<=r)
        return make_pair(seg[pp][p].max,seg[pp][p].max2);

    int mid=(seg[pp][p].l+seg[pp][p].r)>>1;
    if(r<=mid)
        return queryMax(pp,p<<1,l,r);
    else
        if(l>mid)
            return queryMax(pp,p<<1|1,l,r);
        else{
            int temp[4];
            pair<int,int>temp1=queryMax(pp,p<<1,l,mid);
            temp[0]=temp1.first;
            temp[1]=temp1.second;
            temp1=queryMax(pp,p<<1|1,mid+1,r);
            temp[2]=temp1.first;
            temp[3]=temp1.second;
            sort(temp,temp+4);
            return make_pair(temp[3],temp[2]);
        }
}

int main(){
    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++){
        scanf("%d%d",X+i,Y+i);
        s.insert(make_pair(make_pair(X[i],Y[i]),i));
    }

    build(0,1,1,n);
    build(1,1,1,n);

    for(;q;q--){
        int ll,rr;
        scanf("%d%d",&ll,&rr);

        pair<int,int>U=queryMax(1,1,ll,rr);
        pair<int,int>D=queryMin(1,1,ll,rr);
        pair<int,int>L=queryMin(0,1,ll,rr);
        pair<int,int>R=queryMax(0,1,ll,rr);

        int temp=max(U.first-D.first,R.first-L.first);

        auto iter=s.lower_bound(make_pair(make_pair(L.first,D.first),ll));
        if(iter!=s.end()&&iter->first==make_pair(L.first,D.first)&&iter->second<=rr){
            temp=min(temp,max(U.first-D.second,R.first-L.second));
        }

        iter=s.lower_bound(make_pair(make_pair(R.first,D.first),ll));
        if(iter!=s.end()&&iter->first==make_pair(R.first,D.first)&&iter->second<=rr){
            temp=min(temp,max(U.first-D.second,R.second-L.first));
        }

        iter=s.lower_bound(make_pair(make_pair(L.first,U.first),ll));
        if(iter!=s.end()&&iter->first==make_pair(L.first,U.first)&&iter->second<=rr){
            temp=min(temp,max(U.second-D.first,R.first-L.second));
        }

        iter=s.lower_bound(make_pair(make_pair(R.first,U.first),ll));
        if(iter!=s.end()&&iter->first==make_pair(R.first,U.first)&&iter->second<=rr){
            temp=min(temp,max(U.second-D.first,R.second-L.first));
        }

        printf("%d\n",temp);
    }

    return 0;
}
/*
4 1
3 3
5 7
8 3
10 3
1 4
*/