#include "hpmq.h"
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<r;++i)

typedef long long i64;

const int N=500007;

struct Line{
	//ax+by<c
	int a,b,c;//|a|,|b|<=1000; b!=0; |c|<=1000000
};

struct Pos{
	int x,y;
	Data d;
}ps[N];

int dim=0;

double A,B;

struct Node{
	Node *c[2];
	Operation t;
	Data d;
	int x0,x1,y0,y1,S;
	void dn(){
		if(t.empty())return;
		c[0]->apply(t);
		c[1]->apply(t);
		t.clr();
	}
	void up(){
		d.add(c[0]->d,c[1]->d);
	}
	void apply(const Operation &t0){
		t0.apply(t);
		t0.apply(d);
	}
	void init(const Pos &p){
		x0=x1=p.x;
		y0=y1=p.y;
		d=p.d;
		t.clr();
		S=0;
	}
	void init(Node *c0,Node *c1){
		c[0]=c0;
		c[1]=c1;
		t.clr();
		up();
		x0=std::min(c0->x0,c1->x0);
		x1=std::max(c0->x1,c1->x1);
		y0=std::min(c0->y0,c1->y0);
		y1=std::max(c0->y1,c1->y1);
		S=0;
	}
	int op(const Line &l){
		if(std::min(l.a*x0,l.a*x1)+std::min(l.b*y0,l.b*y1)>=l.c)return 0;
		if(std::max(l.a*x0,l.a*x1)+std::max(l.b*y0,l.b*y1)<=l.c)return S=2;
		int S0=c[0]->op(l);
		int S1=c[1]->op(l);
		if(S0==2&&S1==2){
			c[0]->S=c[1]->S=0;
			return S=2;
		}
		if(S0|S1)return S=1;
		return S=0;
	}
	void op(const Operation &o,Data &ans){
		if(!S)return;
		if(S==2){
			ans.add_eq(d);
			apply(o);
			S=0;
			return;
		}
		dn();
		c[0]->op(o,ans);
		c[1]->op(o,ans);
		up();
		S=0;
	}
	bool operator<(const Node&w)const{
		#ifdef D4
		return (x0-w.x0)*A+(y0-w.y0)*B<0;
		#else
		#ifdef SEG
		return (y0<w.y0);
		#else
		//return dim?(x0+y0<w.x0+w.y0):(y0-x0<w.y0-w.x0);
		return dim?(x0<w.x0):(y0<w.y0);
		#endif
		#endif
	}
}ns[N*2],*rt,*np;
std::mt19937 mt(time(0));
Node* build(Node*l,Node*r){
	if(r-l==1)return l;
	double a0=mt()/4294967296.*2*acos(-1);
	A=cos(a0);
	B=sin(a0);
	//A=mt()%2001-1000;
	//B=mt()%2001-1000;
	Node*m=l+(r-l)/2;
	std::nth_element(l,m,r);
	#ifdef D4
	if(r-l>=4){
		Node *m1=l+(m-l)/2,*m2=0,*m2x=m+(r-m)/2;
		double L=0,R=acos(-1);
		while(R-L>1e-12){
			double M=L+(R-L)/2;
			A=cos(a0+M);
			B=sin(a0+M);
			std::nth_element(l,m1,m);
			Node *m2a=std::lower_bound(m,r,m1[-1]);
			Node *m2b=std::lower_bound(m2a,r,*m1);
			//if(r-l>=1000)fprintf(stderr,"%g: %d %d %d\n",M,int(m2a-m),int(m2b-m2a),int(r-m2b));
			if(m2b<m2x)L=M,m2=m2b;
			else if(m2a>m2x)R=M,m2=m2a;
			else{
				std::nth_element(m2a,m2x,m2b);
				m2=m2x;
				break;
			}
		}
		//if(r-l>=1000)fprintf(stderr,"[%d %d  %d %d]\n",m1-l,m-m1,m2-m,r-m2);
		Node *w1,*w2,*w;
		if(m<m2&&m2<r&&std::abs(m2-m2x)<=2){
			w1=np++;
			w1->init(build(l,m1),build(m1,m));
			w2=np++;
			w2->init(build(m,m2),build(m2,r));
			w=np++;
			w->init(w1,w2);
			return w;
		}
	}
	#endif
	dim^=1;
	Node *c0=build(l,m);
	Node *c1=build(m,r);
	dim^=1;
	Node *w=np++;
	w->init(c0,c1);
	
	return w;
}

int t;
void cal(int n){
	if(n<4){
		t+=n;
		return;
	}
	t+=4;
	int n1=n/2,n2=n-n1;
	cal(n1-n1/2);
	cal(n2/2);
	cal(n2-n2/2);
}
void solve(
	const int n,
	const int m,
	const int *x,
	const int *y,
	const Data *d,
	const int *a,
	const int *b,
	const int *c,
	const Operation *o){
	np=ns+n;
	F(i,0,n)ps[i]=Pos{x[i],y[i],d[i]};
	F(i,0,n){
		ns[i].init(ps[i]);
	}
	rt=build(ns,ns+n);
	//cal(n);
	//fprintf(stderr,">>> %lld\n",1ll*q*t);
	F(i,0,m){
		Line ln=Line{a[i],b[i],c[i]};
		Operation t=o[i];
		Data ans;
		ans.clr();
		rt->op(ln);
		rt->op(t,ans);
		ans.print();
	}
}