首先发现一个性质：对于一组询问，如果答案不是 \(-1\)，那么必然存在最优正方形满足，要么三个边界上存在给定的点，要么两个边界 + 一个对角上存在给定的点，这是因为如果一个正方形只顶住了两个边界，那么如果这两个边界是邻边的话正方形肯定可以继续扩大，如果是对边的话我们可以将正方形水平方向上移动直到其卡住另一个点或者这两个点之一处于对角位置。
这样我们考虑钦定一个点在边界上，不妨假设是下边界，那么考虑什么样的边长 \(l\) 是合法的：考虑纵坐标在 \((y_i,y_i+l)\) 区间中的所有点，找到 \(x_i\) 的前驱 \(x_j\) 和后继 \(x_k\)，那么充要条件是 \(x_k-x_j>l\)。
显然这个 \(l\) 满足可二分性，使用主席树上二分可以做到 \(O(n\log n)\)。具体来说，我们将所有点按 \(x\) 从小到大排序，第 \(i\) 棵主席树上 \([l,r]\) 区间位置上我们维护前 \(i\) 个点中，\(y_j\in[l,r]\) 的点里 \(x_j\) 的最大值。对后缀也类似地建主席树。这样上文中提到的“前驱”和“后继”就可以表示为两棵主席树上的一段区间 \(\min\) 和 \(\max\)，用类似线段树二分的手段解决即可。
这样二分出 \(l\) 之后，这个正方形就唯一确定了，这是因为如果上述“前驱”和“后继”都存在并且差值刚好等于 \(l\)，那前驱和后继都在正方形边界上，正方形唯一确定。否则的话，正方形不能继续扩大的原因肯定是因为左上角或者右上角有一个点卡住了正方形，也可以确定正方形的位置。
这样相当于有 \(O(n)\) 个正方形，每个正方形有个权值，求覆盖每个点的矩形中权值的最大值。使用线段树 + 扫描线可以做到 \(O(n\log^2n)\)，但是不够优秀。假设我们在 \(x\) 方向上扫描线，那么我们发现，对于两个矩形 \(A,B\)，如果 \(A\) 的右边界比 \(B\) 靠右并且 \(A\) 的边长比 \(B\) 小，那么在 \(B\) 加入之时 \(A\) 就没用了，所以将线段树上每个节点的 set 替换为单调队列，然后每次区间插入时就仿照单调队列的插入即可做到 \(O(n\log n)\)。
const int MAXN=3e5+5;
const int MAXP=MAXN<<6;
const int LIM=3e8;
const int INF=0x3f3f3f3f;
int n,qu,x[MAXN+5],y[MAXN+5],kx[MAXN+5],ky[MAXN+5],pos[MAXN+5];
int qx[MAXN+5],qy[MAXN+5],kqx[MAXN+5],kqy[MAXN+5];
struct HJTree{
struct node{int ch[2],mn;}s[MAXP+5];
int r1[MAXN+5],r2[MAXN+5],ncnt;
void build(int &k,int l,int r){
if(!k)k=++ncnt;s[k].mn=INF;if(l==r)return;int mid=l+r>>1;
build(s[k].ch[0],l,mid);build(s[k].ch[1],mid+1,r);
}
int modify(int k,int l,int r,int p,int v){
int z=++ncnt;s[z]=s[k];chkmin(s[z].mn,v);
if(l==r)return z;int mid=l+r>>1;
if(p<=mid)s[z].ch[0]=modify(s[k].ch[0],l,mid,p,v);
else s[z].ch[1]=modify(s[k].ch[1],mid+1,r,p,v);
return z;
}
int query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return s[k].mn;int mid=l+r>>1;
if(qr<=mid)return query(s[k].ch[0],l,mid,ql,qr);
else if(ql>mid)return query(s[k].ch[1],mid+1,r,ql,qr);
else return min(query(s[k].ch[0],l,mid,ql,mid),query(s[k].ch[1],mid+1,r,mid+1,qr));
}
int walk_right(int k1,int k2,int l,int r,int p,int lmn1,int lmn2){
if(min(s[k1].mn,lmn1)+min(s[k2].mn,lmn2)>=ky[r]-ky[p])return -1;
if(l==r)return l;int mid=l+r>>1;
if(p>mid)return walk_right(s[k1].ch[1],s[k2].ch[1],mid+1,r,p,lmn1,lmn2);
else{
int t=walk_right(s[k1].ch[0],s[k2].ch[0],l,mid,p,lmn1,lmn2);
if(~t)return t;
return walk_right(s[k1].ch[1],s[k2].ch[1],mid+1,r,p,
min(lmn1,query(s[k1].ch[0],l,mid,max(p,l),mid)),
min(lmn2,query(s[k2].ch[0],l,mid,max(p,l),mid)));
}
}
int walk_left(int k1,int k2,int l,int r,int p,int rmn1,int rmn2){
if(min(s[k1].mn,rmn1)+min(s[k2].mn,rmn2)>=ky[p]-ky[l])return -1;
if(l==r)return l;int mid=l+r>>1;
if(p<=mid)return walk_left(s[k1].ch[0],s[k2].ch[0],l,mid,p,rmn1,rmn2);
else{
int t=walk_left(s[k1].ch[1],s[k2].ch[1],mid+1,r,p,rmn1,rmn2);
if(~t)return t;
return walk_left(s[k1].ch[0],s[k2].ch[0],l,mid,p,
min(rmn1,query(s[k1].ch[1],mid+1,r,mid+1,min(p,r))),
min(rmn2,query(s[k2].ch[1],mid+1,r,mid+1,min(p,r))));
}
}
}T;
struct bar{
int x,y,l;bar(){x=y=l=0;}
bar(int _x,int _y,int _l){x=_x;y=_y;l=_l;}
}z[MAXN*4+5];int cnt=0;
int y_qx[MAXN+5],id_qx[MAXN+5],res[MAXN+5];
vector<tuple<int,int,int,int> >qv[MAXN+5];
struct segtree{
struct node{int l,r,hd;vector<pii>q;}s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r)return;int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void insert(int k,int l,int r,int lim,int v){
if(l<=s[k].l&&s[k].r<=r){
while(s[k].hd<s[k].q.size()&&s[k].q.back().se<=v)s[k].q.ppb();
if(s[k].hd==s[k].q.size()||s[k].q.back().fi<=lim)s[k].q.push_back(mp(lim,v));
return;
}
int mid=s[k].l+s[k].r>>1;
if(r<=mid)insert(k<<1,l,r,lim,v);
else if(l>mid)insert(k<<1|1,l,r,lim,v);
else insert(k<<1,l,mid,lim,v),insert(k<<1|1,mid+1,r,lim,v);
}
int calc(int k,int x,int y){
while(s[k].hd<s[k].q.size()&&s[k].q[s[k].hd].fi<x)s[k].hd++;
return (s[k].hd==s[k].q.size())?0:s[k].q[s[k].hd].se;
}
int query(int k,int x,int y){
if(s[k].l==s[k].r)return calc(k,x,y);int mid=s[k].l+s[k].r>>1;
return max(calc(k,x,y),(y<=mid)?query(k<<1,x,y):query(k<<1|1,x,y));
}
}S;
int main(){
scanf("%d%d",&n,&qu);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
x[++n]=LIM+1;y[n]=LIM+1;x[++n]=-LIM-1;y[n]=LIM+2;
x[++n]=LIM+2;y[n]=-LIM-1;x[++n]=-LIM-2;y[n]=-LIM-2;
for(int i=1;i<=n;i++)kx[i]=x[i],ky[i]=y[i];
sort(kx+1,kx+n+1);sort(ky+1,ky+n+1);
for(int i=1;i<=n;i++){
x[i]=lower_bound(kx+1,kx+n+1,x[i])-kx;
y[i]=lower_bound(ky+1,ky+n+1,y[i])-ky;
pos[x[i]]=y[i];
}
T.build(T.r1[0],1,n);T.build(T.r2[n+1],1,n);
for(int i=1;i<=n;i++)T.r1[i]=T.modify(T.r1[i-1],1,n,pos[i],-kx[i]);
for(int i=n;i;i--)T.r2[i]=T.modify(T.r2[i+1],1,n,pos[i],kx[i]);
for(int i=1;i<=n-4;i++){
int p=T.walk_right(T.r1[x[i]-1],T.r2[x[i]+1],1,n,y[i],INF,INF);if(p==-1)p=n;
int vl=T.query(T.r1[x[i]-1],1,n,y[i],p-1),vr=T.query(T.r2[x[i]+1],1,n,y[i],p-1);
if(vl+vr<=ky[p]-ky[y[i]])z[++cnt]=bar(-vl,ky[y[i]],vl+vr);
else z[++cnt]=bar(-vl,ky[y[i]],ky[p]-ky[y[i]]),z[++cnt]=bar(vr-(ky[p]-ky[y[i]]),ky[y[i]],ky[p]-ky[y[i]]);
p=T.walk_left(T.r1[x[i]-1],T.r2[x[i]+1],1,n,y[i],INF,INF);if(p==-1)p=1;
vl=T.query(T.r1[x[i]-1],1,n,p+1,y[i]),vr=T.query(T.r2[x[i]+1],1,n,p+1,y[i]);
if(vl+vr<=ky[y[i]]-ky[p])z[++cnt]=bar(-vl,ky[y[i]]-(vl+vr),vl+vr);
else z[++cnt]=bar(-vl,ky[y[i]]-(ky[y[i]]-ky[p]),(ky[y[i]]-ky[p])),z[++cnt]=bar(vr-(ky[y[i]]-ky[p]),ky[y[i]]-(ky[y[i]]-ky[p]),ky[y[i]]-ky[p]);
}
for(int i=1;i<=qu;i++)scanf("%d%d",&qx[i],&qy[i]),kqx[i]=qx[i],kqy[i]=qy[i];
sort(kqx+1,kqx+qu+1);sort(kqy+1,kqy+qu+1);
for(int i=1;i<=qu;i++){
int _x=lower_bound(kqx+1,kqx+qu+1,qx[i])-kqx;
int _y=lower_bound(kqy+1,kqy+qu+1,qy[i])-kqy;
y_qx[_x]=_y;id_qx[_x]=i;
}
for(int i=1;i<=cnt;i++){
int xl=upper_bound(kqx+1,kqx+qu+1,z[i].x)-kqx;
int xr=lower_bound(kqx+1,kqx+qu+1,z[i].x+z[i].l)-kqx-1;
int yl=upper_bound(kqy+1,kqy+qu+1,z[i].y)-kqy;
int yr=lower_bound(kqy+1,kqy+qu+1,z[i].y+z[i].l)-kqy-1;
if(xl>xr||yl>yr)continue;
qv[xl].pb(mt(yl,yr,xr,z[i].l));
}
S.build(1,1,qu);
for(int i=1;i<=qu;i++){
sort(qv[i].begin(),qv[i].end(),[&](auto x,auto y){return get<2>(x)<get<2>(y);});
for(auto t:qv[i])S.insert(1,get<0>(t),get<1>(t),get<2>(t),get<3>(t));
res[id_qx[i]]=S.query(1,i,y_qx[i]);
}
for(int i=1;i<=qu;i++)printf("%d\n",(res[i]>1.5e8)?-1:res[i]);
return 0;
}
/*
4 1
1 1
3 3
0 4
6 0
2 2
*/