#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=250050;
int x[N],y[N],l[N],r[N];
ll ans[N];
int n,q;

ll sq(int x){
	return (ll)x*x;
}

ll Dist(int i,int j){
	return sq(x[i]-x[j])+sq(y[i]-y[j]);
}

const ll inf=1e18;
const ll H=1e9;

const int L=27;
unordered_map<ll,int> last[L];
int ptr[L];
vector<int> Qs[N];

const int S=500;
const int B=N/S+5;
ll mn[L][N],mnBlock[L][B];
void Set(int lvl,int i,ll x){
	mn[lvl][i]=min(mn[lvl][i],x);
	mnBlock[lvl][i/S]=min(mnBlock[lvl][i/S],x);
}
ll Get(int lvl,int l,int r){
	ll ans=inf;
	int L=l/S;
	int R=r/S;
	if(L==R){
		for(int i=l;i<=r;i++){
			ans=min(ans,mn[lvl][i]);
		}
	}else{
		for(int i=l;i<(L+1)*S;i++){
			ans=min(ans,mn[lvl][i]);
		}
		for(int i=L+1;i<R;i++){
			ans=min(ans,mnBlock[lvl][i]);
		}
		for(int i=R*S;i<=r;i++){
			ans=min(ans,mn[lvl][i]);
		}
	}
	return ans;
}
int main(){
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%i %i",&x[i],&y[i]);
	}
	for(int i=1;i<=q;i++){
		scanf("%i %i",&l[i],&r[i]);
		Qs[r[i]].pb(i);
	}
	for(int j=0;j<L;j++){
		for(int i=1;i<=n;i++){
			mn[j][i]=inf;
			mnBlock[j][i/S]=inf;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<L;j++){
			int X=x[i]>>j;
			int Y=y[i]>>j;
			if(last[j].count(X*H+Y)){
				ptr[j]=max(ptr[j],last[j][X*H+Y]+1);
			}
			last[j][X*H+Y]=i;
			for(int dx=-2;dx<=2;dx++){
				for(int dy=-2;dy<=2;dy++){
					if(dx==0 && dy==0)continue;
					if(last[j].count((X+dx)*H+(Y+dy))){
						int idx=last[j][(X+dx)*H+(Y+dy)];
						ll dist=Dist(i,idx);
						Set(j,idx,dist);
					}
				}
			}
		}
		for(int qi:Qs[i]){
			int lvl=-1;
			for(int j=L-1;~j;j--){
				if(ptr[j]<=l[qi]){
					lvl=j;
					break;
				}
			}
			if(lvl==-1)ans[qi]=0;
			else{
				ans[qi]=Get(lvl,l[qi],r[qi]);
			}
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}