#include<bits/stdc++.h>
using namespace std;
int x[300005],y[300005],X[300005],Y[300005];
vector<pair<int,int>>g[300005];
long long ans[300005];
int n,q;
long long c[300005];
void add(int x,long long s){
	while(x<=n){
		c[x]=min(c[x],s);
		x+=x&-x;
	}
}
long long query(int x){
	long long ans=1e18;
	while(x){
		ans=min(ans,c[x]);
		x-=x&-x;
	}
	return ans;
}
long long sqr(int x){
	return 1ll*x*x;
}
long long jl(int a,int b){
	return sqr(x[a]-x[b])+sqr(y[a]-y[b]);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=q;++i){
		int l,r;
		scanf("%d%d",&l,&r);
		g[r].emplace_back(l,i);
		ans[i]=1e18;
	}
	map<pair<int,int>,int>mp;
	int mx=0;
	for(int i=1;i<=n;++i){
		int wz=mp[make_pair(x[i],y[i])];
		mx=max(mx,wz);
		for(auto pi:g[i]){
			if(pi.first<=mx)ans[pi.second]=0;
		}
		mp[make_pair(x[i],y[i])]=i;
	}
	for(int k=0;k<=26;++k){
		set<pair<pair<int,int>,int>>se;
		priority_queue<pair<int,pair<int,int>>>es;
		for(int i=1;i<=n;++i)c[i]=1e18;
		for(int i=1;i<=n;++i){
			X[i]=x[i]>>(k+1),Y[i]=y[i]>>(k+1);
			int mx=0;
			for(int dx=-1;dx<=1;++dx){
				auto pi=make_pair(X[i]+dx,Y[i]-1);
				auto it=se.lower_bound(make_pair(pi,0));
				while(it!=se.end()){
					auto au=(*it).first;
					if(au.first>pi.first||au.second>pi.second+2)break;
					int sc=(*it).second;
					long long cd=jl(sc,i);
					add(n-sc+1,cd);
					if(cd<=1ll*(1<<k)*(1<<k))mx=max(mx,sc);
					++it;
				}
			}
			while(es.size()&&-es.top().first<=mx){
				auto xx=es.top();
				es.pop();
				se.erase(make_pair(xx.second,-xx.first));
			}
			for(auto cx:g[i]){
				int wz=cx.first,zz=cx.second;
				ans[zz]=min(ans[zz],query(n-wz+1));
			}
			se.emplace(make_pair(X[i],Y[i]),i);
			es.emplace(-i,make_pair(X[i],Y[i]));
		}
	}
	for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
	return 0;
}