#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define i64 __int128
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define d(i,j) 1ll*j*1813327743ll+i
const ll N = 3e5+5,inf = 1e18;
ll n,Q,B,nodex,mn[N],mn_B[N],b[N],R[N],ans[N],L[N];
int dx[10]={-1,-1,-1,0,0,0,1,1,1},dy[10]={-1,0,1,-1,0,1,-1,0,1};
struct node{
	ll x,y;
}p[N];
vector<pii> q[N];
vector<int> pos[N*30];
gp_hash_table<ll,int> num[30];
ll calc(ll sx,ll sy,ll ex,ll ey){
	return (sx-ex)*(sx-ex)+(sy-ey)*(sy-ey);
}
ll ask(ll l,ll r){
	ll res = inf;
	for(int i=l;i<=min(R[b[l]],r);i++) res = min(res,mn[i]);
	for(int i=b[l]+1;i<=b[r]-1;i++) res = min(res,mn_B[i]);
	for(int i=L[b[r]];i<=r;i++) res = min(res,mn[i]);
	return res;
}
int main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> Q;
	B = sqrt(n);
	for(int i=1;i<=n;i++){
		cin >> p[i].x >> p[i].y;
		b[i] = (i-1)/B+1;
		R[b[i]] = i;
		if(b[i]!=b[i-1]) L[b[i]] = i;
	}
	for(int i=1,l,r;i<=Q;i++){
		cin >> l >> r;
		q[r].pb({l,i});
	}
	for(int i=1;i<=n;i++) mn[i] = mn_B[i] = inf;
	for(int i=1;i<=n;i++){
		for(int j=0;(1<<j)<=1e8;j++){
			ll tx = (p[i].x)>>j,ty = (p[i].y)>>j;
			if(num[j].find(d(tx,ty))==num[j].end()) num[j][d(tx,ty)] = ++nodex;
			for(int k=0;k<9;k++){
				ll nx = tx+dx[k],ny = ty+dy[k]; 
				if(nx<0 || ny<0 || num[j].find(d(nx,ny))==num[j].end()) continue;
				int id = num[j][d(nx,ny)];
				vector<int> tmp;
				for(int l:pos[id]){
					ll dis = calc(p[l].x,p[l].y,p[i].x,p[i].y);
					mn[l] = min(mn[l],dis),mn_B[b[l]] = min(mn_B[b[l]],dis);
					if(dis>(1ll<<(2*j-2))) tmp.pb(l);
				}
				pos[id] = tmp;
				if(k==4) pos[id].pb(i);
			}
		}
		for(pii t:q[i]) ans[t.se] = ask(t.fi,i);
	}
	for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
	return 0;
}