#include #include #include #include #define REP(i,a,b) for(i=a;ik);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);} void intIntIntSort(int d[],int m1[],int m2[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m1[i];m1[i]=m1[j];m1[j]=t;t=m2[i];m2[i]=m2[j];m2[j]=t;}intIntIntSort(d,m1,m2,i);intIntIntSort(d+j+1,m1+j+1,m2+j+1,s-j-1);} typedef struct struct_intfenwick{ int size, memory; int *data; }intFenwickTree; intFenwickTree intFenwickTreeNew(int memory){ intFenwickTree res; res.memory=memory; res.data=(int*)malloc(memory*sizeof(int)); return res; } void intFenwickTreeDelete(intFenwickTree *t){free(t->data);} void intFenwickTreeInit(intFenwickTree *t, int size){int i; t->size=size; rep(i,size) t->data[i]=0;} int intFenwickTreeAdd(intFenwickTree *t,int k,int add){while(ksize)t->data[k]+=add, k|=k+1;} int intFenwickTreeGet(intFenwickTree *t,int k){int res=0; while(k>=0)res+=t->data[k],k=(k&(k+1))-1; return res;} int x[1000000], y[1000000], xy[1000000]; int qx[1000000], qy[1000000], qd[1000000], qxy[1000000], qind[1000000], res[1000000]; int main(){ int T, N, Q; int i, j, k, loop; int st; intFenwickTree tx = intFenwickTreeNew(610000); intFenwickTree ty = intFenwickTreeNew(610000); T = 1; while(T--){ assert( scanf("%d%d",&N,&Q)==2 ); assert( 1<=N && N<=300000 ); assert( 1<=Q && Q<=200000 ); rep(i,N) assert( scanf("%d%d",x+i,y+i)==2 ); rep(i,Q) assert( scanf("%d%d%d",qx+i,qy+i,qd+i)==3 ); rep(i,N) assert( 1<=x[i]&&x[i]<=300000 && 1<=y[i]&&y[i]<=300000 ); rep(i,Q) assert( 1<=qx[i]&&qx[i]<=300000 && 1<=qy[i]&&qy[i]<=300000 && 1<=qd[i]&&qd[i]<=300000 ); /* sorting points and queries accourding to x+y */ /* here, we count the number of points on left under of triangles*/ rep(i,N) xy[i] = x[i]+y[i]; intIntIntSort(xy,x,y,N); rep(i,Q) qxy[i] = qx[i]+qy[i]+qd[i], qind[i]=i; intIntSort(qxy, qind, Q); intFenwickTreeInit(&tx, 610000); intFenwickTreeInit(&ty, 610000); st = 0; rep(loop, Q){ k = qind[loop]; while(st < N && xy[st] <= qxy[loop]){ intFenwickTreeAdd(&tx, x[st], 1); intFenwickTreeAdd(&ty, y[st], 1); st++; } res[k] = st; res[k] -= intFenwickTreeGet(&tx, qx[k]-1); res[k] -= intFenwickTreeGet(&ty, qy[k]-1); } /* sorting points and queries accourding to x */ /* here, we count the number of points on left of triangles */ /* and under of triangles */ /* double count is already decreased in the above */ intIntSort(x,y,N); rep(i,Q) qxy[i] = qx[i], qind[i] = i; intIntSort(qxy, qind, Q); intFenwickTreeInit(&ty, 610000); st = 0; rep(loop,Q){ k = qind[loop]; while(st < N && x[st] < qx[k]){ intFenwickTreeAdd(&ty, y[st], 1); st++; } res[k] += intFenwickTreeGet(&ty, qy[k]-1); } rep(i,Q) printf("%d\n",res[i]); } return 0; }