#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2.5e5+5;
const int sqN=505;
int n,sq,q;
ll x[MAXN],y[MAXN],bx[MAXN],by[MAXN],p[MAXN];
ll ans[MAXN];
vector<int> sp[MAXN];
vector<pair<int,int> > que[MAXN];
struct ds{
// O(1)-O(sqrt(n)) 单点改、区间 min 
int le[MAXN],ri[MAXN],bel[MAXN],tot;
ll minn[sqN],val[MAXN];
void build(){
	sq=sqrt(n);
	while(ri[tot]!=n){
		le[tot+1]=ri[tot]+1;ri[tot+1]=min(le[tot+1]+sq,n);
		++tot;
	}
	for(int i=1;i<=tot;i++){
		for(int j=le[i];j<=ri[i];j++) bel[j]=i,val[j]=1e18; 
		minn[i]=1e18;
	} 
} 
void modify(int x,ll v){
	minn[bel[x]]=min(minn[bel[x]],v);val[x]=min(val[x],v);
}
ll ask(int l,int r){
	ll ans=1e18;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) ans=min(ans,val[i]);
		return ans; 
	}
	for(int i=l;i<=ri[bel[l]];i++) ans=min(ans,val[i]);
	for(int i=bel[l]+1;i<bel[r];i++) ans=min(ans,minn[i]);
	for(int i=le[bel[r]];i<=r;i++) ans=min(ans,val[i]);
	return ans; 
}
}B; 
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int k=0;k<=30;k++){
		map<pair<int,int>,pair<int,int> > mp;
		for(int i=1;i<=n;i++) bx[i]=x[i]>>k,by[i]=y[i]>>k,p[i]=i;
		sort(p+1,p+n+1,[&](int x,int y){return (bx[x]!=bx[y]?bx[x]<bx[y]:(by[x]!=by[y]?by[x]<by[y]:x<y));});
		for(int l=1,r;l<=n;l=r+1){
			r=l;
			while(r<n&&bx[p[r+1]]==bx[p[l]]&&by[p[r+1]]==by[p[l]]) r++;
			mp[MP(bx[l],by[l])]=MP(l,r);
		}
		auto add=[&](int l,int t,int x){for(int i=t;i>=t-5&&i>=l;i--) sp[x].push_back(p[i]);};
		for(auto i:mp){
			int x=i.first.first,y=i.first.second,l=i.second.first,r=i.second.second;
			for(int dx:{x-1,x,x+1}) for(int dy:{y-1,y,y+1}) if(mp.count(MP(dx,dy))){
				int L=mp[MP(dx,dy)].first,R=mp[MP(dx,dy)].second;
				int j=-1;
				for(int i=l;i<=r;i++){
					while(j+1<=R&&p[j+1]<p[i]) j++;
					add(L,j,p[i]);
				}
			}
		}
	}
	B.build();
	for(int i=1;i<=q;i++){
		int l,r;cin>>l>>r;
		que[r].push_back(MP(l,i));
	}
	for(int i=1;i<=n;i++){
		for(int j:sp[i]) if(j<i) B.modify(j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		for(auto q:que[i]) ans[q.second]=B.ask(q.first,i);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}