#include<bits/stdc++.h> #define int long long //#define double long double #define endl "\n" using namespace std; int n,q; const double rt2=sqrtl(2); double eps=1e-7; struct node{ double x,y; }; inline double disA(node A,node B){ return abs(A.y+A.x-B.y-B.x)/2*rt2; } inline double disB(node A,node B){ return abs(A.y-A.x-B.y+B.x)/2*rt2; } inline node val(node A,node B){ if(A.x>B.x)swap(A,B); double x=(A.x+B.x-(B.y-A.y))/2; double y=A.y-(x-A.x); return {x,y}; } inline node top(node A,node B){ if(A.x>B.x)swap(A,B); double x=(A.x+B.x+(B.y-A.y))/2; double y=A.y+(x-A.x); return {x,y}; } inline double area(node A,node B){ if(A.x>B.x)swap(A,B); node V=val(A,B); return disB(A,V)*disA(V,B); } inline double area(node A,node L,node R){ return disA(L,A)*disB(A,R); } inline node top(node L,node R,double x){ double lim=top(L,R).x; if(x<=lim) return {x,L.y+x-L.x}; else return {x,R.y+R.x-x}; } map<double,double>mp; inline double ER(double x){ auto itr=mp.upper_bound(x); auto itl=mp.lower_bound(x); auto it=itl; itl--; node L={itl->first,itl->second},R={itr->first,itr->second}; node A={it->first,it->second}; double res=area(A,L,R); mp.erase(it); return res; } //const double tt=rt2/2; struct ASK{ double x,y; int id,val; inline void trs(){ double ax=x,ay=y; x=ax+ay; y=ay-ax; } }; vector<ASK>P; inline double fd(double x,bool h,node l,node r){ node L,R; if(!h){ auto itl=mp.upper_bound(x); itl--; auto itr=mp.lower_bound(x); L={itl->first,itl->second},R={itr->first,itr->second}; } else L=l,R=r; double lim=val(L,R).x; double res=0; if(x<=lim) res=L.y-(x-L.x); else res=R.y-(R.x-x); return res; } inline void INS(double x,double S,int id){ while(1){ auto itl=mp.upper_bound(x); itl--; auto itr=mp.lower_bound(x); node L={itl->first,itl->second},R={itr->first,itr->second}; double s=area(top(L,R,x),L,R); if(s>S){ double l=fd(x,1,L,R),r=1e8; while(fabsl(r-l)>=1e-7){ double mid=(l+r)/2; if(area({x,mid},L,R)<=S)l=mid; else r=mid; } mp[x]=l; assert(l>=abs(x)); P.push_back({x,l,0,id}); return ; } double lim=top(L,R).x; if(x==lim){ S+=ER(L.x); if(itl!=itr) S+=ER(R.x); } else if(x>lim)S+=ER(R.x); else S+=ER(L.x); } } struct ND{ int x,y,val,id; }; vector<ND>T; inline bool cmp(ND A,ND B){ return A.x==B.x?A.y>B.y:A.x>B.x; } int ANS[300300]; int ct=0; int nx,ny; double X[600300]; double Y[600300]; inline void UN(){ sort(X+1,X+ct+1); sort(Y+1,Y+ct+1); X[0]=-1e18; Y[0]=-1e18; for(int i=1;i<=ct;i++){ if(X[i]-X[nx]>eps)nx++; X[nx]=X[i]; if(Y[i]-Y[ny]>eps)ny++; Y[ny]=Y[i]; } return ; cout<<nx<<endl; for(int i=1;i<=nx;i++) cout<<X[i]<<" "; cout<<endl; cout<<ny<<endl; for(int i=1;i<=ny;i++) cout<<Y[i]<<" "; cout<<endl; } int t[600300]; inline int lb(int x){ return x&-x; } inline void mod(int x,int k){ while(x) t[x]=min(t[x],k),x-=lb(x); } inline int g(int x){ int res=n+1; while(x<=6e5+2) res=min(res,t[x]),x+=lb(x); return res; } signed main(){ //freopen("snow.in","r",stdin); //freopen("snow.out","w",stdout); double LIM=1e8; mp[-LIM]=LIM; mp[LIM]=LIM; P.push_back({-LIM,LIM,0,0}); P.push_back({LIM,LIM,0,0}); ios::sync_with_stdio(0); memset(t,0x3f,sizeof(t)); cin>>n>>q; for(int i=1;i<=n;i++){ double S,x; cin>>S>>x; INS(x,S,i); } for(int i=1;i<=q;i++){ double x,y; ANS[i]=n+1; cin>>x>>y; y=fd(x,0,{0.,0.},{0.,0.})-y; //cout<<x<<"x"<<y<<endl; //cout<<i<<" "<<x<<" "<<y<<" "<<fd(x)<<endl; P.push_back({x,y,i,-1}); } for(ASK &A:P){ A.trs(); X[++ct]=A.x; Y[ct]=A.y; } UN(); for(ASK &A:P){ //if(A.id)cout<<A.id<<" "<<A.x<<"x"<<A.y<<" "; int x=lower_bound(X+1,X+nx+1,A.x)-X; int y=lower_bound(Y+1,Y+ny+1,A.y)-Y; //if(A.id)cout<<x<<"x"<<y<<endl; //cout<<A.x<<" "<<A.y<<" "<<x<<" "<<y<<" "<<A.val<<" "<<A.id<<endl; T.push_back({x,y,A.val,A.id}); } sort(T.begin(),T.end(),cmp); for(auto A:T) if(A.id){ ANS[A.id]=g(A.y); } else { mod(A.y,A.val); } for(int i=1;i<=q;i++) cout<<ANS[i]<<endl; cout.flush(); return 0; }