#include <iostream>
#include <algorithm>
#include <assert.h>
#include <string>
#include <vector>
using namespace std;

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}


struct point{
	long long x;
	long long y;
};
bool operator<(point a,point b){
	if(a.x==b.x){
		return a.y<b.y;
	}
	return a.x<b.x;
}

bool is_left(point a,point b,point c){
	long long x1=b.x-a.x;
	long long y1=b.y-a.y;
	long long x2=c.x-b.x;
	long long y2=c.y-b.y;

	return x1*y2 - x2*y1 >= 0;
}

bool is_right(point a,point b,point c){
	long long x1=b.x-a.x;
	long long y1=b.y-a.y;
	long long x2=c.x-b.x;
	long long y2=c.y-b.y;

	return x1*y2 - x2*y1 <= 0;
}

vector<point> convex(vector<point> a){
	if(a.size() == 1){
		return a;
	}
	sort(a.begin(),a.end());
	vector<point> upper,lower,ret;
	int upr=0,lwr=0;
	int n=a.size();
	for(int i=0;i<n;i++){
		while(upr > 1 && is_left(upper[upr-2],upper[upr-1],a[i])){
			upr--;
			upper.pop_back();
		}
		while(lwr > 1 && is_right(lower[lwr-2],lower[lwr-1],a[i])){
			lwr--;
			lower.pop_back();
		}
		upper.push_back(a[i]);
		lower.push_back(a[i]);
		lwr++;
		upr++;
	}
	upper.pop_back();
	while(lower.size()> 0){
		upper.push_back(lower.back());
		lower.pop_back();
	}
	upper.pop_back();
	return upper;
}


int n,q;
vector<point> sgt[400400];
point arr[100100];


void build(int nd,int l,int r){
	if(l==r){
		sgt[nd].push_back(arr[l]);
		return;
	}
	int mid=(r+l)/2;
	build(2*nd,l,mid);
	build(2*nd+1,mid+1,r);
	vector<point> pts=sgt[2*nd];
	/*for(int i=0;i<sgt[2*nd].size();i++){
		pts.push_back(sgt[2*nd][i]);
	}*/
	for(int i=0;i<sgt[2*nd+1].size();i++){
		pts.push_back(sgt[2*nd+1][i]);
	}
	sgt[nd]=convex(pts);
}

vector<point> query(int nd,int l,int r,int s,int e){
	if(s<=l && r<=e){
		return sgt[nd];
	}
	int mid=(r+l)/2;
	vector<point> pts;
	if(s<=mid){
		pts=query(2*nd,l,mid,s,e);
	}
	if(mid+1<=e){
		vector<point> tm = query(2*nd+1,mid+1,r,s,e);
		for(int i=0;i<tm.size();i++){
			pts.push_back(tm[i]);
		}
	}
	return convex(pts);
}


int main(){
	n=readIntLn(1,100000);
	for(int i=1;i<=n;i++){
		arr[i].x = readIntSp(1,1000000000);
		arr[i].y = readIntLn(1,1000000000);
	}
	build(1,1,n);
	q=readIntLn(1,100000);
	while(q--){
		int l,r;
		l=readIntSp(1,n);
		r=readIntLn(l,n);
		vector<point> a=query(1,1,n,l,r);
		long long ans=0;
		for(int i=0;i<a.size();i++){
			for(int j=i+1;j<a.size();j++){
				ans = max(ans,(a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));
			}
		}
		printf("%lld\n",ans);
	}
	assert(getchar()==-1);
}