#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 int L=27;
map<pair<int,int>,int> last[L];
int ptr[L];
vector<int> Qs[N];

ll mn[L][N];
void Set(int lvl,int i,ll x){
	for(;i>0;i-=i&-i){
		mn[lvl][i]=min(mn[lvl][i],x);
	}
}
ll Get(int lvl,int i){
	ll ans=inf;
	for(;i<=n;i+=i&-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;
		}
	}
	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,Y})){
				ptr[j]=max(ptr[j],last[j][{X,Y}]+1);
			}
			last[j][{X,Y}]=i;
			for(int dx=-1;dx<=1;dx++){
				for(int dy=-1;dy<=1;dy++){
					if(dx==0 && dy==0)continue;
					if(last[j].count({X+dx,Y+dy})){
						int idx=last[j][{X+dx,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]);
			}
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}