/*
Sakurajima Mai,
Eriri Spencer,
Izumi Sagiri,
Keqing,
Hu tao,
Ganyu
say,"With our sincere wishes to HHX: never to debug code"
*/

#include<bits/stdc++.h>
#define R register
#define ll long long
#define random mt19937
const int QWQ=250005;
using namespace std;
inline int read(){
	int x=0,f=1; char ch=getchar();
	while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
	while (isdigit(ch)){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
	return x*f;
} 
int n,q,id[QWQ],pos[QWQ]; ll res[QWQ];
pair<int,int> din[QWQ]; double com[QWQ]; 
vector<pair<int,int> > ques[QWQ];
inline int max(const int &x,const int &y){ return x>y ? x:y; }
inline int min(const int &x,const int &y){ return x<y ? x:y; }
inline ll powr(const int &x){ return (ll)x*x; }
inline ll getlen(const int &i,const int &j){
	return powr(din[i].first-din[j].first)+powr(din[i].second-din[j].second);
} 
inline bool cmp(const int &i,const int &j){ return com[i]<com[j]; }
namespace work{
	const int inf=0x3f3f3f3f3f3f3f3f;
	const int block=500;
	ll ta[QWQ],tb[QWQ];
	inline void init(){
		for (R int i=0;i<QWQ;i++)
			ta[i]=tb[i]=inf;
	}
	inline void add(int x,ll d){
		ta[x]=min(ta[x],d);
		tb[x/block]=min(tb[x/block],d);
	}
	inline ll ask(int l,int r){
		ll res=inf; int ls=l/block,rs=r/block;
		if (ls==rs){
			for (R int i=l;i<=r;i++)
				res=min(res,ta[i]);
			return res;
		} for (R int i=l;i<(ls+1)*block;i++) res=min(res,ta[i]);
        for (R int i=rs*block;i<=r;i++) res=min(res,ta[i]);
        for (R int i=ls+1;i<rs;i++) res=min(res,tb[i]);
        return res;
	}
}
signed main(){
	n=read(),q=read();
	random rand(10086);
	for (R int i=1;i<=n;i++)
		din[i].first=read(),din[i].second=read(); 
	for (R int i=1;i<=q;i++){
		int l=read(),r=read();
		ques[r].push_back({l,i});
	}
	double rl=(rand()%100000000+1)/100000000.0*2*acos(-1.0);
//	double rl=1145141919810ll;
	double siin=sin(rl),coos=cos(rl);
	for (R int i=1;i<=n;i++)
		com[i]=din[i].first*coos-din[i].second*siin,id[i]=i;
	sort(id+1,id+1+n,cmp);
	for (R int i=1;i<=n;i++)
		pos[id[i]]=i;
	work::init();
	for (R int i=1;i<=n;i++){
		for (R int j=max(1,i-1000);j<i;j++)
			work::add(j,getlen(j,i));
		for (R int j=max(1,pos[i]-1000);j<=min(n,pos[i]+1000);j++)
			if (id[j]<i) work::add(id[j],getlen(id[j],i));
		for (auto j:ques[i]) res[j.second]=work::ask(j.first,i);
	} for (R int i=1;i<=q;i++) printf("%lld\n",res[i]);
	return 0;
}