#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double eps=1e-6;
int n,q,B;
struct node{
	double x,y;
	int id;
	bool operator <(const node &b)const{
		if(abs(x-b.x)>eps)return x<b.x;
		else return y<b.y;
	}
}a[250005];
int b[250005];
int pos[250005],L[505],R[505];
vector<pair<int,int> > Query[250005];
ll ans[250005];
ll val[250005],mn[505];
ll getdis(double x,double y,double xx,double yy){return (ll)round((x-xx)*(x-xx)+(y-yy)*(y-yy));}
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,int r){
	ll res=0x3f3f3f3f3f3f3f3f;
	if(pos[l]==pos[r])for(int i=l;i<=r;i++)res=min(res,val[i]);
	else{
		for(int i=pos[l]+1;i<pos[r];i++)res=min(res,mn[i]);
		for(int i=l;i<=R[pos[l]];i++)res=min(res,val[i]);
		for(int i=L[pos[r]];i<=r;i++)res=min(res,val[i]);
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&q);B=sqrt(n);
	double cs=1.0*rand()/RAND_MAX,sn=sqrt(1-cs*cs);
	for(int i=1;i<=n;i++){
		double x,y;
		scanf("%lf%lf",&x,&y);
		a[i].x=x*cs-y*sn,a[i].y=x*sn+y*cs;
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		b[a[i].id]=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,r;scanf("%d%d",&l,&r);
		Query[r].push_back(make_pair(l,i));
	}
	init();
	for(int i=1;i<=n;i++){
		for(int j=max(1,b[i]-1000);j<b[i];j++)add(a[j].id,getdis(a[j].x,a[j].y,a[b[i]].x,a[b[i]].y));
		for(auto p:Query[i])ans[p.second]=ask(p.first,i);
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}