#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define Yes printf("Yes\n")
#define No printf("No\n")
#define pb push_back
const ll N=5e6+10;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_cxx;
using namespace __gnu_pbds;

ll nt[9][2]={0,0,0,-1,-1,0,0,1,1,0,1,-1,-1,1,-1,-1,1,1};
ll n,q;
ll X[N],Y[N];
vector<pair<ll,ll>>query[N];
vector<ll>a[N];
ll blo,b[N],ma[N],mb[N];
ll ans[N];

ll num;
gp_hash_table<ll,ll>vis[N];

ll ask(ll l,ll r){
	ll ans=1e18;
	if(b[l]==b[r]){
		For(i,l,r)ans=min(ans,ma[i]);
	}else{
		for(ll i=l;b[i]==b[l];++i)ans=min(ans,ma[i]);
		For(i,b[l]+1,b[r])ans=min(ans,mb[i]);
	}
	return ans;
}

void solve(){
	
	ll V=1e8;
	scanf("%lld%lld",&n,&q);
	blo=sqrt(n);
	For(i,1,n){
		scanf("%lld%lld",&X[i],&Y[i]);
		b[i]=(i-1)/blo+1;
		ma[i]=mb[i]=1e18;
	}
	For(i,1,q){
		ll l,r;
		scanf("%lld%lld",&l,&r);
		query[r].pb({l,i});
		ans[i]=1e18;
	}
	For(r,1,n){
		for(ll j=1;(1<<j)<=V;++j){
			ll x=X[r]>>j,y=Y[r]>>j;
			ll t=V>>j;
			ll id=(x<<32)|y;
			if(!vis[j].count(id))vis[j][id]=++num;
			For(k,0,8){
				ll xx=x+nt[k][0],yy=y+nt[k][1];
				ll ID=(xx<<32)|yy;
				if(xx<0||xx>t||yy<0||yy>t)continue;
				if(!vis[j].count(ID))continue;
				vector<ll>tmp;
				for(ll l:a[vis[j][ID]]){
					ll dis=(X[r]-X[l])*(X[r]-X[l])+(Y[r]-Y[l])*(Y[r]-Y[l]);
					ma[l]=min(ma[l],dis),mb[b[l]]=min(mb[b[l]],dis);
					if(dis>=(1ll<<j+j-2))tmp.pb(l);
				}
				if(!k)tmp.pb(r);
				a[vis[j][ID]]=tmp;
			}
		}
		for(auto &[x,y]:query[r])ans[y]=ask(x,r);
	}
	For(i,1,q)printf("%lld\n",ans[i]);
	
}
int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

answer.code: In function ‘void solve()’:
answer.code:58:36: error: ‘class __gnu_pbds::gp_hash_table<long long int, long long int>’ has no member named ‘count’
   58 |                         if(!vis[j].count(id))vis[j][id]=++num;
      |                                    ^~~~~
answer.code:63:44: error: ‘class __gnu_pbds::gp_hash_table<long long int, long long int>’ has no member named ‘count’
   63 |                                 if(!vis[j].count(ID))continue;
      |                                            ^~~~~
answer.code:74:27: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   74 |                 for(auto &[x,y]:query[r])ans[y]=ask(x,r);
      |                           ^
answer.code:40:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         scanf("%lld%lld",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
answer.code:43:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |                 scanf("%lld%lld",&X[i],&Y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
answer.code:49:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |                 scanf("%lld%lld",&l,&r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~