#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

const int N=250010;
const double eps=1e-9;
inline int sign(double x)
{
	return fabs(x)<eps?0:(x>0?1:-1);
}

int n,Q,X[N],Y[N],ord[N];
mt19937 rng(time(0)^rand()^(*(new int)));

const int B=400;
namespace DS
{
	int bel[N],L[N],R[N];
	ll f[N],g[N];
	void init()
	{
		rep(i,1,n) bel[i]=(i-1)/B+1;
		rep(i,1,n) R[bel[i]]=i;
		drep(i,n,1) L[bel[i]]=i;
		memset(f,0x3f,sizeof(f));
		memset(g,0x3f,sizeof(g));
	}
	void update(int x,ll v)
	{
		f[x]=min(f[x],v);
		g[bel[x]]=min(g[bel[x]],v);
	} 
	ll q(int l)
	{
		ll ans=1e18;
		rep(i,l,R[bel[l]]) ans=min(ans,f[i]);
		rep(i,bel[l]+1,bel[n]) ans=min(ans,g[i]);
		return ans;
	} 
}

ll ans[N];
vector<array<int,2> > vec[N];
ll dis(int x,int y)
{
	return 1ll*(X[x]-X[y])*(X[x]-X[y])+1ll*(Y[x]-Y[y])*(Y[x]-Y[y]);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin>>n>>Q;
	rep(i,1,n) cin>>X[i]>>Y[i];
	rep(i,1,n) ord[i]=i;
	int angle=rng();
	sort(ord+1,ord+n+1,[&](int i,int j) -> bool
	{
		if (i==j) return 0;
		double xi=X[i]*cos(angle)-Y[i]*sin(angle),yi=Y[i]*cos(angle)+X[i]*sin(angle);
		double xj=X[j]*cos(angle)-Y[j]*sin(angle),yj=Y[j]*cos(angle)+X[j]*sin(angle);
		return sign(xi-xj)==0?yi<yj:xi<xj;
	});
	DS::init();
	
	rep(i,1,Q)
	{
		int l,r; cin>>l>>r;
		vec[r].push_back({l,i});
	}
	
	rep(i,1,n)
	{
		rep(j,max(1,i-3*B),i-1) DS::update(j,dis(i,j));
		rep(j,max(1,i-3*B),min(n,i+3*B)) if (ord[j]<i) DS::update(ord[j],dis(i,ord[j]));
		for (auto x:vec[i])
		{
			ans[x[1]]=DS::q(x[0]);
		}
	}
	
	rep(i,1,Q) printf("%lld\n",ans[i]);
	
	return 0;
}