#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M=2.5e5+5;
struct point{int x,y;}a[M];
int n,q,blk,idx,qr[M],bel[M];
ll ans[M],rec[M],sum1[M],sum2[M];
vector<pair<int,int>>qry[M];
unordered_map<ll,int>mp[28];
vector<int>vec[M*28];
ll dist(point a,point b){
	return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);
}
int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x;
}
void update(int x,ll p){
	sum1[bel[x]]=min(sum1[bel[x]],p);sum2[x]=min(sum2[x],p);
}
ll query(int x){ ll ans=LLONG_MAX;
	for (int i=bel[x]+1;i<=bel[n];i++) ans=min(ans,sum1[i]);
	for (int i=x;i<=qr[bel[x]];i++) ans=min(ans,sum2[i]);
	return ans;
}
int main(){
	n=read();q=read();blk=ceil(sqrt(n));
	for (int i=1;i<=n;i++) rec[i]=sum1[i]=sum2[i]=LLONG_MAX;
	for (int i=1;i<=n;i++) bel[i]=(i-1)/blk+1;
	for (int i=1;i<=bel[n];i++) qr[i]=qr[i-1]+blk;
	for (int i=1;i<=n;i++) a[i]={read(),read()};
	for (int i=1;i<=q;i++){
		int l=read(),r=read();
		qry[r].emplace_back(l,i);
	}
	for (int i=1;i<=n;i++){
		for (int k=0;k<28;k++){
			for (auto x:{-1,0,1})
				for (auto y:{-1,0,1}){
					ll Hash=((a[i].x>>k)+x)<<30|((a[i].y>>k)+y);
					if (!mp[k].count(Hash)) continue;
					int num=mp[k][Hash];
					vector<int>tmp;int pos=0;
					for (auto x:vec[num]){
						ll tmp=dist(a[x],a[i]);
						if (tmp<rec[x]) update(x,rec[x]=tmp);
						if (tmp<1ll<<(k<<1)) pos=x;
					}
					for (auto x:vec[num]) if (x>pos)
						tmp.emplace_back(x);
					swap(tmp,vec[num]);
				}
			ll Hash=(a[i].x>>k)<<30|(a[i].y>>k);
			if (!mp[k].count(Hash)) mp[k][Hash]=idx++;
			vec[mp[k][Hash]].emplace_back(i);
		}
		for (auto [j,id]:qry[i])
			ans[id]=query(j);
	}
	for (int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}