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

vector<pair<int,int>> all[L];
vector<vector<int>> nxt[L];

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;
			all[j].pb({X,Y});
		}
	}
	for(int j=0;j<L;j++){
		sort(all[j].begin(),all[j].end());
		all[j].erase(unique(all[j].begin(),all[j].end()),all[j].end());
		for(int i=0;i<all[j].size();i++){
			int X=all[j][i].first;
			int Y=all[j][i].second;
			vector<int> go;
			for(int dx=-3;dx<=3;dx++){
				for(int dy=-3;dy<=3;dy++){
					if(dx==0 && dy==0)continue;
					if(abs(dx)==3 && abs(dy)==3)continue;
					int nx=X+dx;
					int ny=Y+dy;
					int k=lower_bound(all[j].begin(),all[j].end(),make_pair(nx,ny))-all[j].begin();
					if(k<all[j].size() && all[j][k].first==nx && all[j][k].second==ny){
						go.pb(k);
					}
				}
			}
			nxt[j].pb(go);
		}
		last[j].resize(all[j].size());
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<L;j++){
			int X=x[i]>>j;
			int Y=y[i]>>j;
			int k=lower_bound(all[j].begin(),all[j].end(),make_pair(X,Y))-all[j].begin();
			if(last[j][k]){
				ptr[j]=max(ptr[j],last[j][k]+1);
			}
			last[j][k]=i;
			auto Try=[&](int p){
				if(p!=-1 && p!=k){
					int idx=last[j][p];
					ll dist=Dist(i,idx);
					Set(j,idx,dist);
				}
			};
			for(int o=0;o<nxt[j][k].size();o++){
				Try(nxt[j][k][o]);
			}
		}
		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;
}