#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+(c^'0'),c=getchar();
	return x;
}
#define ll long long
int n,q,B;
const int S=500;
ll x[250005],y[250005];
double ex[250005],ey[250005];
int a[250005],b[250005];
bool cmp(int x,int y){return ex[x]<ex[y];}
int pos[250005],L[505],R[505];
vector<pair<int,int> > Query[250005];
ll ans[250005];
ll val[250005],mn[505];
ll getdis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
void init(){
	for(int i=1;i<=n;i++)val[i]=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=pos[n];i++)mn[i]=0x3f3f3f3f3f3f3f3f;
}
void add(int x,ll y){
	val[x]=min(val[x],y);
	mn[pos[x]]=min(mn[pos[x]],y);
}
ll ask(int l){
	ll res=0x3f3f3f3f3f3f3f3f;
	for(int i=pos[l]+1;i<=pos[n];i++)res=min(res,mn[i]);
	for(int i=l;i<=R[pos[l]];i++)res=min(res,val[i]);
	return res;
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
//	puts("OK");
	n=read(),q=read();B=sqrt(n);
	double cs=cos(114514),sn=sin(114514);
	for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(),ex[i]=x[i]*cs-y[i]*sn,ey[i]=x[i]*sn+y[i]*cs;
	for(int i=1;i<=n;i++)a[i]=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)b[a[i]]=i;
	for(int i=1;i<=n;i++){
		pos[i]=(i-1)/B+1;
		if(!L[pos[i]])L[pos[i]]=i;
		R[pos[i]]=i;
	}
	for(int i=1;i<=q;i++){
		int l=read(),r=read(); 
		Query[r].push_back(make_pair(l,i));
	}
	init();
	for(int i=1;i<=n;i++){
		int lim=min(n,b[i]+S);
		for(int j=max(1,b[i]-S);j<=lim;j++)if(a[j]<i)add(a[j],getdis(b[j],i));
		for(int j=max(1,i-S);j<i;j++)add(j,getdis(j,i));
		for(auto p:Query[i])ans[p.second]=ask(p.first);
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}