#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define Yes printf("Yes\n")
#define No printf("No\n")
#define pb push_back
const ll N=5e6+10;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_cxx;
using namespace __gnu_pbds;

ll nt[9][2]={0,0,0,-1,-1,0,0,1,1,0,1,-1,-1,1,-1,-1,1,1};
ll n,q;
ll X[N],Y[N];
vector<pair<ll,ll>>query[N];
vector<ll>a[N];
ll blo,b[N],ma[N],mb[N];
ll ans[N];

ll num;
gp_hash_table<ll,ll>vis[N];

ll ask(ll l,ll r){
	ll ans=1e18;
	if(b[l]==b[r]){
		For(i,l,r)ans=min(ans,ma[i]);
	}else{
		for(ll i=l;b[i]==b[l];++i)ans=min(ans,ma[i]);
		For(i,b[l]+1,b[r])ans=min(ans,mb[i]);
	}
	return ans;
}

void solve(){
	
	ll V=1e8;
	scanf("%lld%lld",&n,&q);
	blo=sqrt(n);
	For(i,1,n){
		scanf("%lld%lld",&X[i],&Y[i]);
		b[i]=(i-1)/blo+1;
		ma[i]=mb[i]=1e18;
	}
	For(i,1,q){
		ll l,r;
		scanf("%lld%lld",&l,&r);
		query[r].pb({l,i});
		ans[i]=1e18;
	}
	For(r,1,n){
		for(ll j=1;(1<<j)<=V;++j){
			ll x=X[r]>>j,y=Y[r]>>j;
			ll t=V>>j;
			ll id=(x<<32)|y;
			if(vis[j].find(id)!=vis[j].end())vis[j][id]=++num;
			For(k,0,8){
				ll xx=x+nt[k][0],yy=y+nt[k][1];
				ll ID=(xx<<32)|yy;
				if(xx<0||xx>t||yy<0||yy>t)continue;
				if(vis[j].find(ID)!=vis[j].end())continue;
				vector<ll>tmp;
				for(ll l:a[vis[j][ID]]){
					ll dis=(X[r]-X[l])*(X[r]-X[l])+(Y[r]-Y[l])*(Y[r]-Y[l]);
					ma[l]=min(ma[l],dis),mb[b[l]]=min(mb[b[l]],dis);
					if(dis>=(1ll<<j+j-2))tmp.pb(l);
				}
				if(!k)tmp.pb(r);
				a[vis[j][ID]]=tmp;
			}
		}
		for(auto &[x,y]:query[r])ans[y]=ask(x,r);
	}
	For(i,1,q)printf("%lld\n",ans[i]);
	
}
int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)solve();
	return 0;
}