#include<bits/stdc++.h>
#define int long long
#define MAXN 250010
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
const int S=500;
const int N=100000000;
const int mod=300007;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,Q,ans[MAXN];
int x[MAXN],y[MAXN];
vector<pii>que[MAXN];
struct Block{
	int bel[MAXN],lb[MAXN],rb[MAXN],cnt;
	int val[MAXN],mx[MAXN];
	void init(int n){
		cnt=0;
		for(int l=1;l<=n;l+=S){
			lb[++cnt]=l;rb[cnt]=min(n,l+S-1);
			for(int i=lb[cnt];i<=rb[cnt];i++)bel[i]=cnt,val[i]=mx[i]=inf;
		}
	}
	void update(int pos,int v){val[pos]=min(val[pos],v);mx[bel[pos]]=min(mx[bel[pos]],v);}
	int query(int l,int r){
		int bl=bel[l],br=bel[r];
		if(bl==br){
			int ret=inf;
			for(int i=l;i<=r;i++)ret=min(ret,val[i]);
			return ret;
		}
		int ret=inf;
		for(int i=l;i<=rb[bl];i++)ret=min(ret,val[i]);
		for(int i=lb[br];i<=r;i++)ret=min(ret,val[i]);
		for(int i=bl+1;i<br;i++)ret=min(ret,mx[i]);
		return ret;
	}
}ds;
struct hshtable{
	int head[mod+3],nxt[MAXN],st[MAXN],val[MAXN],cnt;
	void clear(){
		for(int i=1;i<=cnt;i++)nxt[i]=val[i]=0;
		memset(head,0,sizeof(head));cnt=0;
	}
	void insert(int x,int v){
		int key=x%mod;
		for(int i=head[key];i;i=nxt[i])
			if(st[i]==x)return (void)(val[i]=v);
		st[++cnt]=x;val[cnt]=v;
		nxt[cnt]=head[key];head[key]=cnt;
	}
	int operator[](int x){
		int key=x%mod;
		for(int i=head[key];i;i=nxt[i])
			if(st[i]==x)return val[i];
		return 0;
	}
}buc[30];
int get(int x,int y){return x*N+y;}
int dis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
vector<int>pos[MAXN<<5];
int ql[MAXN<<5],lmt[30],tot;
void add(int k,int p){
	int qx=x[p]/(2<<k),qy=y[p]/(2<<k);
	int px=(x[p]/(1<<k)*(1<<k)==qx*(2<<k)),py=(y[p]/(1<<k)*(1<<k)==qy*(2<<k));
	for(int i=qx-(!px);i<=qx+px;i++)
		for(int j=qy-(!py);j<=qy+py;j++){
			if(i<0||j<0)continue;
			int now=buc[k][get(i,j)];if(!now)continue;
			for(int t=ql[now];t<(int)pos[now].size();t++){
				int np=pos[now][t];
				if(np<=lmt[k]){ql[now]=t+1;continue;}
				int d=dis(np,p);ds.update(np,d);
				if(d<=(1<<k))lmt[k]=max(lmt[k],np),ql[now]=t+1;
			}
		}
	int now=buc[k][get(qx,qy)];
	if(!now)now=++tot,buc[k].insert(get(qx,qy),tot);
	pos[now].pb(p);
}
signed main(){
	scanf("%lld%lld",&n,&Q);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);
	for(int i=1;i<=Q;i++){
		int l,r;scanf("%lld%lld",&l,&r);
		que[r].pb(mp(l,i));
	}ds.init(n);
	for(int i=1;i<=n;i++){
		for(int k=0;k<=28;k++)add(k,i);
		int pre=buc[29][get(x[i],y[i])];
		if(pre)ds.update(pre,0);
		buc[29].insert(get(x[i],y[i]),i);
		for(auto j:que[i])ans[j.se]=ds.query(j.fi,i);
	}
	for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);
	return 0;
}