#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+(c^'0'),c=getchar();
	return x;
}
#define ll long long
int n,q;
ll x[250005],y[250005];
vector<pair<int,int> > Query[250005];
ll ans[250005];
ll getdis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
namespace BLOCK{
	int B;
	int pos[250005],L[505],R[505];
	ll val[250005],mn[505];
	void init(){
		B=sqrt(n);
		for(int i=1;i<=n;i++){
			pos[i]=(i-1)/B+1;
			if(!L[pos[i]])L[pos[i]]=i;
			R[pos[i]]=i;
		}
	}
	void clear(){
		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,int y){
		ll dis=getdis(x,y);
		val[x]=min(val[x],dis);
		mn[pos[x]]=min(mn[pos[x]],dis);
	}
	ll ask(int l){
		ll res=0x3f3f3f3f3f3f3f3f;
		for(int i=pos[l]+1;i<=pos[n];i++)res=min(res,mn[i]);
		for(int i=l;i<=R[pos[l]];i++)res=min(res,val[i]);
		return res;
	}
}
using BLOCK::init;
using BLOCK::clear;
using BLOCK::add;
using BLOCK::ask;
unordered_map<ll,int> mp;
vector<vector<int>>vec;
ll get(int x,int y){return x*(ll)1e8+y;}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
//	puts("OK");
	n=read(),q=read();
	for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
	for(int i=1;i<=q;i++){
		int l=read(),r=read(); 
		Query[r].push_back(make_pair(l,i));
	}
	init();
	memset(ans,0x3f,sizeof(ans));
	for(int j=0;j<27;j++){
		mp.clear();vec.clear();
		clear();
		for(int i=1;i<=n;i++){
			int xx=x[i]>>j,yy=y[i]>>j;
			for(int p=-1;p<=1;p++)for(int q=-1;q<=1;q++){
				ll id=get(xx+p,yy+q);
				if(mp.find(id)!=mp.end()){
					int pos=mp[id];
					for(int k:vec[pos])add(k,i);
				}
			}
			ll id=get(xx,yy);
			if(mp.find(id)==mp.end()){
				mp[id]=vec.size(),vec.push_back({i});
				continue;
			}
			int pos=mp[id];
			vector<int> newvec;newvec.push_back(i);
			for(int p:vec[pos])if(j&&getdis(p,i)>(1ll<<2*j-2))newvec.push_back(p);
			vec[pos]=newvec;
			for(auto p:Query[i])ans[p.second]=min(ans[p.second],ask(p.first));
		}
//		printf("j=%d\n",j);
	}
//	printf("%.3lfs\n",clock()*1.0/CLOCKS_PER_SEC);
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}