#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#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 emplace_back
const ll N=5e6+10;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;}

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[35];

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;
	n=read(),q=read();
	blo=sqrt(n);
	For(i,1,n){
		X[i]=read(),Y[i]=read();
		b[i]=(i-1)/blo+1;
		ma[i]=mb[i]=1e18;
	}
	For(i,1,q){
		ll l,r;
		l=read(),r=read();
		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;
				ll SB=vis[j][ID];
				vector<ll>tmp;
				for(ll l:a[SB]){
					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[SB]=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;
}