#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=2.5e5+9,INF=(1ll<<60ll);
ll n,q,S,X[N],Y[N],blk[N],val[N],bel[N],ans[N],id[N];
vector<pii>vq[N];
vector<ll>to[N];
unordered_map<ll,pii>mp;
ll Dis(ll i,ll j){
	return (X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
}
ll Id(ll i,ll j){
	return (i<<30ll)+j;
}
void Upd(ll x,ll y){
	blk[bel[x]]=min(blk[bel[x]],y);
	val[x]=min(val[x],y);
}
ll Query(ll p){
	ll res=INF;
	for(ll i=p;bel[i]==bel[p];++i)res=min(res,val[i]);
	rep(i,bel[p]+1,bel[n])res=min(res,blk[i]);
	return res;
}
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	n=read(),q=read(),S=sqrt(n);
	rep(i,1,n)X[i]=read(),Y[i]=read();
	rep(i,1,q){
		ll l=read(),r=read();
		vq[r].emplace_back(make_pair(l,i));
		ans[i]=INF;
	}
	rep(i,1,n)bel[i]=(i-1)/S+1;
	rep(d,0,27){
		mp.clear();
		rep(i,1,n)id[i]=i;
		sort(id+1,id+n+1,[&](ll i,ll j){
			return (X[i]>>d)==(X[j]>>d)?(X[i]>>d)<(X[j]>>d):(Y[i]>>d)<(Y[j]>>d);
		});
		ll l=1;
		while(l<=n){
			ll r=l;
			while(r<n&&(X[id[l]]>>d)==(X[id[r+1]]>>d)&&(Y[id[l]]>>d)==(Y[id[r+1]]>>d))r++;
			sort(id+l,id+r+1);
			mp[Id(X[id[l]]>>d,Y[id[l]]>>d)]=make_pair(l,r);
			rep(i,l,r){
				rep(j,i+1,min(r,i+3))to[id[j]].push_back(id[i]);
			}
			l=r+1;
		}
		l=1;
		while(l<=n){
			ll r=l,px=(X[id[l]]>>d),py=(Y[id[l]]>>d);
			while(r<n&&px==(X[id[r+1]]>>d)&&py==(Y[id[r+1]]>>d))r++;
			vector<pii>vdir={{-1,1},{0,1},{1,1},{1,0}};
			for(pii dir:vdir){
				ll dx=dir.first,dy=dir.second;
				if(mp.count(Id(px+dx,py+dy))){
					pii pi=mp[Id(px+dx,py+dy)];
					ll ql=pi.first,qr=pi.second;
					vector<ll>vc;
					vc.insert(vc.end(),id+l,id+r+1);
					vc.insert(vc.end(),id+ql,id+qr+1);
					inplace_merge(vc.begin(),vc.begin()+r-l+1,vc.end());
					rep(i,0,(ll)vc.size()-1){
						rep(j,i+1,min((ll)vc.size()-1,i+3))to[vc[j]].push_back(vc[i]);
					}
				}
			}
			l=r+1;
		}
	}
	rep(i,1,n)blk[i]=val[i]=INF;
	rep(i,1,n){
		for(ll j:to[i])Upd(j,Dis(j,i));
		for(pii qd:vq[i])ans[qd.second]=min(ans[qd.second],Query(qd.first));
	}
	rep(i,1,q)write(ans[i]),putchar('\n');
	return 0;
}