#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;short f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;return;
}
#define ll long long
#define N 260000
struct phash{
	size_t operator()(const pair<int,int>&p)const
	{
		return 1234567u*p.first+p.second;
	}
};
__gnu_pbds::cc_hash_table<pair<int,int>,vector<int>,phash>st[28];
int n,q,x[N],y[N];
ll ans[N],s[N];
ll t[N];
void modify(int x,ll v)
{
	for(;x<=n;x+=x&-x)
		t[x]=min(t[x],v);
}
ll query(int x)
{
	ll v=LLONG_MAX;
	for(;x;x-=x&-x)
		v=min(v,t[x]);
	return v;
}
vector<pair<int,int>>v[N];
ll dist(int a,int b){
	return 1ll*(x[a]-x[b])*(x[a]-x[b])+1ll*(y[a]-y[b])*(y[a]-y[b]);
}
int main()
{
	read(n),read(q);
	for(int i=1;i<=n;i++)
		t[i]=s[i]=LLONG_MAX;
	for(int i=1;i<=n;i++)
		read(x[i]),read(y[i]);
	for(int i=1;i<=q;i++)
	{
		int l,r;read(l),read(r);
		v[r].push_back({l,i});
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<28;j++)
		{
			int len=1<<j,cx=x[i]/len,cy=y[i]/len;
			for(int dx=-1;dx<=1;dx++)
				for(int dy=-1;dy<=1;dy++)
				{
					auto it=st[j].find({cx+dx,cy+dy});
					if(it!=st[j].end())
					{
						vector<int>tmp;
						int mx=0;
						for(auto x:it->second)
						{
							if(dist(x,i)<s[n-x+1])
								modify(n-x+1,dist(x,i)),s[n-x+1]=dist(x,i);
							if(dist(x,i)<=1ll *(len/2)*(len/2))
								mx=max(mx,x);
						}
						for(auto x:it->second)
							if(x>mx)
								tmp.push_back(x);
						it->second=tmp;
					}
				}
			st[j][{cx,cy}].push_back(i);
		}
		for(auto [l,id]:v[i]){
			ans[id]=query(n-l+1);
		}
	}
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}