#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,pos[400005],B=512,ans[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];
set<int>s;
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 rr){return (l.x*l.x+l.y*l.y)<(rr.x*rr.x+rr.y*rr.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[_],rt=0;
//		cout<<_<<"\t"<<i<<endl;
		auto o=s.insert(i).first;
		if(o!=s.begin()){
			for(auto t=prev(o);t!=s.begin()&&rt<=50;t--) T.cg(a[*t].id,dis(i,*t)),rt++;//,cout<<(*t)<<",";
			T.cg(a[*s.begin()].id,dis(i,*s.begin()));
		}
//		cout<<*s.begin()<<";";
		rt=0;
		for(auto t=next(o);t!=s.end()&&rt<=50;t++) T.cg(a[*t].id,dis(i,*t)),rt++;//,cout<<(*t)<<",";
//		cout<<endl;
		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;
}