#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
int n,q,cnt,h[250005],L[33];
ll ans[250005],b[888],w[251005];
struct st{
	int x,y;
}a[250005];
vector<int>e[250005],c[250005],p[250005];
gp_hash_table<ll,int>mp;
ll id(int x,int y){
	return x*1000000000+y;
}
void add(int x,int y,int i){
	int t=mp[id(x,y)];
	if(!t) t=mp[id(x,y)]=++cnt;
	p[t].push_back(i);
}
void cg(int x,ll v){
	w[x]=min(w[x],v);
	b[x>>9]=min(b[x>>9],v);
}
ll que(int x){
	ll res=1e18;
	for(;x&511;x++) res=min(res,w[x]);
	for(x>>=9;!(x>>9);x++) res=min(res,b[x]);
	return res;
}
mt19937 rd(time(NULL));
signed main(){
	cin>>n>>q;
	memset(w,0x3f,sizeof(w));
	memset(b,0x3f,sizeof(b));
	for(int i=1;i<=n;i++) scanf("%d %d",&a[i].x,&a[i].y);
	int DX=rd()%999999999,DY=rd()%999999999;
	for(int i=1;i<=n;i++) a[i].x+=DX,a[i].y+=DY;
	for(int i=1;i<=27;i++){
		for(int j=1;j<=cnt;j++) p[j].clear();
		mp.clear(),cnt=0;
		for(int j=1;j<=n;j++){
			int x=a[j].x>>i,y=a[j].y>>i;
			for(int k=-1;k<=1;k++){
				for(int l=-1;l<=1;l++){
					if(mp.find(id(x+k,y+l))!=mp.end()){
						int t=mp[id(x+k,y+l)],d=p[t].size();
						for(int o=max(d-(i<=6?7:7),0);o<d;o++) e[j].push_back(p[t][o]);
					}
				}
			}
			add(a[j].x>>i,a[j].y>>i,j);
		}
	}
	for(int i=1,j;i<=q;i++){
		scanf("%d %d",&h[i],&j);
		c[j].push_back(i);
	}
	for(int i=1;i<=n;i++){
		for(int j:e[i]) if(j<i) cg(j,1ll*(a[i].x-a[j].x)*(a[i].x-a[j].x)+1ll*(a[i].y-a[j].y)*(a[i].y-a[j].y));
		for(int j:c[i]) ans[j]=que(h[j]);
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}