// 那就是希望。
// 即便需要取模，也是光明。

// 复杂度 O(?)

#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
uint X[1000005],Y[1000005];
bol Spec=1;
// ullt T;
inline uint dist(uint u,uint v){
    // T++;
    return(X[u]>X[v]?X[u]-X[v]:X[v]-X[u])+(Y[u]>Y[v]?Y[u]-Y[v]:Y[v]-Y[u]);
}
inline uint dist2(uint u,uint v){
    // T++;
    return X[v]-X[u]+(Y[u]>Y[v]?Y[u]-Y[v]:Y[v]-Y[u]);
}
std::pair<uint,uint>get(std::vector<uint>&P){
    uint u=P[0],v=P[1];uint d=dist(u,v);
    if(Spec){
        for(uint i=0;i+1<P.size();i++)if(_min(d,dist(P[i],P[i+1])))u=P[i],v=P[i+1];
    }else{
        for(uint i=0;i<P.size();i++)for(uint j=1;j<=10&&i+j<P.size();j++)
            if(_min(d,dist2(P[i],P[i+j])))u=P[i],v=P[i+j];
    }
    return{u,v};
}
uint L[1000005],R[1000005],Ans[1000005];
voi dfs(std::vector<uint>&Q,std::vector<uint>&P){
    if(Q.empty())return;
    auto t=get(P);if(t.first>t.second)std::swap(t.first,t.second);
    // printf("%u %u %u %u\n",*std::min_element(P.begin(),P.end()),
    //         t.first,t.second,*std::max_element(P.begin(),P.end()));
    std::vector<uint>_L,_R,_A,_B;
    for(auto s:Q)
        if(R[s]<=t.second)_L.push_back(s);
        else if(L[s]>t.first)_R.push_back(s);
        else Ans[s]=dist(t.first,t.second);
    for(auto s:P)
        if(s<=t.first)_A.push_back(s);
        else if(s<t.second)_A.push_back(s),_B.push_back(s);
        else _B.push_back(s);
    std::vector<uint>().swap(P),std::vector<uint>().swap(Q);
    dfs(_L,_A),dfs(_R,_B);
}
int main()
{
    uint n,q;scanf("%u%u",&n,&q);
    std::vector<uint>P,Q;
    for(uint i=0;i<n;i++){
        int x,y;scanf("%d%d",&x,&y),Spec&=!y;
        X[i]=x+1000000000,Y[i]=y+1000000000;
        P.push_back(i);
    }
    const uint Dist=pow(n+1,0.4)+5;
    for(uint i=0;i<q;i++){
        scanf("%u%u",L+i,R+i),L[i]--;
        if(R[i]-L[i]>Dist)Q.push_back(i);
        else{
            Ans[i]=-1;
            for(uint u=L[i];u<R[i];u++)for(uint v=u+1;v<R[i];v++)
                _min(Ans[i],dist(u,v));
        }
    }
    std::sort(P.begin(),P.end(),[&](uint u,uint v){return X[u]==X[v]?Y[u]<Y[v]:X[u]<X[v];});
    dfs(Q,P);
    // printf("cnt:%llu\n",T);
    for(uint i=0;i<q;i++)printf("%u\n",Ans[i]);
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。