#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define m_p make_pair #define p_b push_back #define pi pair<int,int> #define p1 first #define p2 second #define x1 x114514 #define y1 y114514 #define double long double using namespace std; typedef long long ll; const double sq2=sqrt(2),eps=1e-7; const int maxn=6e5+10,N=6e5; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,q; struct BIT { int t[maxn]; BIT(){memset(t,0x7f,sizeof(t));} int lb(int x){return x&(-x);} void upd(int x,int v){x=N-x+1;for(;x<=N;x+=lb(x))t[x]=min(t[x],v);} int qry(int x){x=N-x+1;int res=2e9;for(;x;x-=lb(x))res=min(res,t[x]);return res;} }T; set<pair<double,double> >s; double F1[maxn],F2[maxn],X[maxn],Y[maxn]; int f1[maxn],f2[maxn],res[maxn]; vector<pi>Q[maxn],ins[maxn]; double g(double x,double y){ double w1=abs((x+y)/2),w2=abs((x-y)/2); w1=w1*sq2,w2=w2*sq2; return w1*w2; } double gg(double x1,double y1,double x2,double y2){ return g(x2-x1,y2-y1); } bool chkout(double x1,double y1,double x2,double y2,double x,double y){ double w=x2-x1-y1+y1;w/=2; double dis=x2-x; return dis>w; } void INS(double x,double S,int id){ // cout<<"test "<<S<<'\n'; auto it=s.lower_bound(m_p(x,0)); if(fabs((*it).p1-x)<eps){ double tx=x; it--; double x1=(*it).p1,y1=(*it).p2; it++; double y=(*it).p2; it++; double x2=(*it).p1,y2=(*it).p2; double w=(x-y-x1+y1)/2; x1+=w,y1-=w; double s1=(x-x1)*sq2; x1=x,y1=y,x=x2,y=y2; w=(x-y-x1+y1)/2; double s2=w*sq2; it--;s.erase(it); // cout<<"test "<<s1*s2<<'\n'; S+=abs(s1*s2); // cout<<"d= "<<s1/sq2<<' '<<s2/sq2<<'\n'; // cout<<"test "<<s1*s2<<'\n'; x=tx; // for(auto it:s)cout<<it.p1<<' '<<it.p2<<'\n'; it=s.lower_bound(m_p(x,0)); } // cout<<"test "<<S<<'\n'; double x1=(*it).p1,y1=(*it).p2; it--; double x2=(*it).p1,y2=(*it).p2; swap(x1,x2),swap(y1,y2); double y,p; bool ff=0; if(chkout(x1,y1,x2,y2,x,y)){ // cout<<"chkout\n"; y=y1+x-x1; double s1=(x-x1)*sq2; double w=y1-x1-y2+x2;w/=2; double s2=w*sq2; p=abs(s1*s2); ff=1; } else { double s1=(x2-((x2-x1-y2+y1)/2+x1))*sq2; y=x2+y2-x; double s2=(x-x2)*sq2; p=abs(s1*s2); } if(p>S){ double w=(x2-x1-y2+y1)/2; x1+=w,y1-=w; // cout<<"test "<<x1<<' '<<y1<<'\n'; double l=abs(x),r=1e9; while(l+eps<r){ double mid=(l+r)/2; if(gg(x1,y1,x,mid)>=S)r=mid; else l=mid; }s.insert(m_p(x,r)); F1[id]=x,F2[id]=r; // cout<<"test "<<x<<' '<<r<<'\n'; // cout<<"test "<<gg(0.75,0.75,0,4)<<'\n'; return; } // cout<<x<<' '<<y<<'\n'; S-=p; if(ff)s.erase(m_p(x1,y1));else s.erase(m_p(x2,y2)); s.insert(m_p(x,y)); INS(x,S,id); } double cal(double h){ auto it=s.lower_bound(m_p(h,0)); double x1=(*it).p1,y1=(*it).p2;it--; double x2=(*it).p1,y2=(*it).p2; swap(x1,x2),swap(y1,y2); double w=(x2-x1-y2+y1)/2.0; // cout<<h<<' '<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<'\n'; if(h<=x1+w)return y1-(h-x1); return y2-(x2-h); } void slv(){ scanf("%d %d",&n,&q); s.insert(m_p(-1e9,1e9)),s.insert(m_p(1e9,1e9)); up(i,1,n){ double s,x; scanf("%Lf %Lf",&s,&x); // cout<<s<<' '<<x<<'\n'; INS(x,s,i); } up(i,1,n){ // cout<<"test "<<F1[i]<<' '<<F2[i]<<'\n'; double w1=-(F1[i]-F2[i])/2; double w2=(F1[i]+F2[i])/2; w1=abs(w1),w2=abs(w2); F1[i]=w1,F2[i]=w2; X[i]=w1,Y[i]=w2; } // cout<<"test "<<s.size()<<'\n'; sort(X+1,X+n+1); sort(Y+1,Y+n+1); up(i,1,n)f1[i]=lower_bound(X+1,X+n+1,F1[i])-X; up(i,1,n)f2[i]=lower_bound(Y+1,Y+n+1,F2[i])-Y; up(i,1,n)ins[f1[i]].p_b(m_p(f2[i],i)); up(i,1,q){ double h,x; scanf("%Lf %Lf",&h,&x); // cout<<"cal: "<<cal(h)<<'\n'; double hh=cal(h)-x; if(hh<abs(h)){ res[i]=0; continue; } x=h;double y=hh; double f1=-(x-y)/2,f2=(x+y)/2; f1=abs(f1),f2=abs(f2); int xx=lower_bound(X+1,X+n+1,f1)-X; int yy=lower_bound(Y+1,Y+n+1,f2)-Y; // if(i==3)cout<<"qry "<<xx<<' '<<yy<<'\n'; Q[xx].p_b(m_p(yy,i)); } down(i,n,1){ for(auto it:ins[i])T.upd(it.p1,it.p2); for(auto it:Q[i])res[it.p2]=T.qry(it.p1); } up(i,1,q)if(res[i]>n)res[i]=0; up(i,1,q)printf("%d\n",res[i]); }int main(){ // freopen("snow.in","r",stdin); // freopen("snow.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }