#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,pos[400005],B=512,ans[400005];
bool t[400005];
struct SEG{
	int r[400005],t[555];
	void init(){
		memset(r,0x3f,sizeof(r));
		memset(t,0x3f,sizeof(t));
	}
	void cg(int x,int v){
		t[x>>9]=min(t[x>>9],v);
		r[x]=min(r[x],v);
	}
	int que(int L,int R){
		int res=1e18;
		for(int i=L;i<=L+B&&i<=R;i++) res=min(res,r[i]);
		for(int i=R;i>=R-B&&i>=L;i--) res=min(res,r[i]);
		for(int i=(L>>9)+1;i<(R>>9);i++) res=min(res,t[i]);
		return res;
	}
}T;
struct st{
	int x,y,id;
}a[400005];
struct qt{
	int l,r;
}c[400005];
vector<int>r[400005];
int dis(int x,int y){
	return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) scanf("%lld %lld",&a[i].x,&a[i].y),a[i].id=i;
	sort(a+1,a+n+1,[&](st l,st r){return (l.x*l.x+l.y*l.y)<(r.x*r.x+r.y*r.y);});
	for(int i=1;i<=n;i++) pos[a[i].id]=i;
	for(int i=1;i<=q;i++){
		scanf("%lld %lld",&c[i].l,&c[i].r);
		r[c[i].r].push_back(i);
	}
	T.init();
	for(int _=1;_<=n;_++){
		int i=pos[_];
		for(int j=max(1ll,i-B);j<=B&&j<=n;j++) if(t[j]) T.cg(a[j].id,dis(i,j));
		t[i]=1;
		for(int j:r[_]) ans[j]=T.que(c[j].l,c[j].r);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}