#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin);
#define Fout(file) freopen(file,"w",stdout);
using namespace std;
const int N=2.5e5+5,M=N*30,V=1e8; using ll = long long;
class STree{;
	int n,B; ll a[N],b[N];
public:	
	void init(int nn) { n=nn; B=sqrt(n)+1; For(i,0,n) a[i]=b[i]=1e18; }
	void poke(int x,ll y) { a[x]=min(a[x],y); b[x/B]=min(b[x/B],y); }
	ll peek(int x) { return min(*min_element(a+x,a+min(n,x/B*B+B-1)+1),*min_element(b+x/B+1,b+n/B+1)); }
}T;
int n,Q,X[N],Y[N],tot; vector<pair<int,int>> qry[N]; vector<int> lis[M]; ll ans[N];
//~ __gnu_pbds::gp_hash_table<ll,int> mp[30];
unordered_map<ll,int> mp[30];
ll dist(int i,int j) { return 1ll*(X[i]-X[j])*(X[i]-X[j])+1ll*(Y[i]-Y[j])*(Y[i]-Y[j]); }
ll ID(int x,int y) { return (ll(x)<<31)+y; }
void update(int u,ll id,int i,bool flg){
	if(mp[i].find(id)==mp[i].end()) mp[i][id]=++tot,assert(tot<M);
	int o=mp[i][id]; vector<int> tmp; if(flg) tmp.push_back(u);
	for(int v:lis[o]){
		ll d=dist(u,v); T.poke(v,d); if(flg&&d>(i==0?0:1ll<<(i*2-2))) tmp.push_back(v);
	}
	lis[o].swap(tmp);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>Q; T.init(n); For(i,1,n) cin>>X[i]>>Y[i];
	For(i,1,Q) { int l,r; cin>>l>>r; qry[r].emplace_back(l,i); ans[i]=1e18; }
	For(r,1,n){
		for(int i=1;(1<<i)<=V;i++){
			int x=X[r]>>i,y=Y[r]>>i;
			For(xx,x-1,x+1) For(yy,y-1,y+1){
				if(xx<0||yy<0||xx>(V>>i)||yy>(V>>i)) continue;
				update(r,ID(xx,yy),i,xx==x&&yy==y);
			}
		}
		for(auto [l,id]:qry[r]) ans[id]=min(ans[id],T.peek(l));
	}
	For(i,1,Q) cout<<ans[i]<<'\n';
	return 0;
}