#include "hpmq.h"
#include<bits/stdc++.h>

#define F(i,l,r) for(int i=l;i<r;++i)

#define pr(...) //fprintf(stderr,__VA_ARGS__)

typedef long long i64;

using std::swap;
using std::sort;

const int B=1007,N=500007;

int n,q,cur_x;

//禁止竖直线，三线共点，直线重合。

bool rev[B];
struct Line{
	//ax+by<c
	int a,b,c,id;//|a|,|b|<=1000; b!=0; |c|<=1000000
	bool operator<(const Line& w)const{
		int k1=a*w.b-b*w.a;
		if(k1)return k1<0;
		return c*w.b-b*w.c<0;
	}
	void init(int a0,int b0,int c0,int x){
		a=a0;
		b=b0;
		c=c0;
		assert(b);
		rev[x]=(b<0);
		if(b<0)a=-a,b=-b,c=-c;
		id=x;
	}
}ls[B],ls0[B];

struct Cmp{
	bool operator()(const Line &w,const Line &u){
		int w1=w.c-w.a*cur_x,w2=w.b;
		int u1=u.c-u.a*cur_x,u2=u.b;
		return w1*u2<u1*w2;
	}
};

struct node{
	node*l,*r,*p;
	int u,d;
	void init(int w){
		l=r=p=0;
		u=w;
		d=w+1;
	}
	void lk(node*w,node*u){
		w->r=this;
		l=w;r=0;p=u;
	}
}ns[B*B],*n0[B],*n1[B];
int np;
int pos[B],pos0[B];

struct Cross{
	int x1,x2;//x=x2/x1
	int w1,w2,key2;
	bool operator<(const Cross& c)const{
		i64 s=i64(x2)*c.x1-i64(x1)*c.x2;
		return s?s<0:key2<c.key2;
	}
	int init(Line &l1,Line &l2,int c){
		x1=l1.a*l2.b-l2.a*l1.b;
		if(!x1)return 0;
		x2=l1.c*l2.b-l1.b*l2.c;
		if(x1<0)x1=-x1,x2=-x2;
		w1=l1.id;
		w2=l2.id;
		key2=c;
		return 1;
	}
}cs[B*B];
int cp=0;

Operation ms[B];

struct Pos{
	int x,y;
	Data d;
	Operation *t;
	void init(int x0,int y0,const Data &d0){
		x=x0;y=y0;d=d0;
		t=0;
	}
	bool operator<(const Pos &w)const{return x<w.x;}
	bool operator<(const Cross &w)const{return x*i64(w.x1)<w.x2;}
}ps[N];

struct node2{
	Operation t;
	Pos p0;
	void init(){
		p0.d.clr();
		t.clr();
	}
	void init(Pos &p){
		p0.x=p.x;
		p0.y=p.y;
		p0.d.add_eq(p.d);
		p.t=&t;
	}
}ns2[B*B*2];
int np2;

namespace KDT{
double A,B;
int dim=0;
struct Node{
	Node *c[2];
	Operation t;
	Data d;
	int x0,x1,y0,y1,S;
	node2 *src;
	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;
		src=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;
		src=0;
	}
	void dna(){
		if(src)return;
		t.apply(c[0]->t);
		t.apply(c[1]->t);
		c[0]->dna();
		c[1]->dna();
	}
	int op(const Line &l){
		//fprintf(stderr,"[%d %d  %d %d] %d %d %d  %d\n",x0,x1,y0,y1,l.a,l.b,l.c,int(std::min(l.a*x0,l.a*x1)+std::min(l.b*y0,l.b*y1)>=l.c));
		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{
		//return (x0-w.x0)*A+(y0-w.y0)*B<0;
		//return dim?(x0+y0<w.x0+w.y0):(y0-x0<w.y0-w.x0);
		return dim?(x0<w.x0):(y0<w.y0);
	}
}Ns[::B*::B*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);
	if(r-l>=4&&0){
		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;
		}
	}
	dim^=1;
	Node *c0=build(l,m);
	Node *c1=build(m,r);
	dim^=1;
	Node *w=Np++;
	w->init(c0,c1);
	
	return w;
}
}


void calc(int m){
	F(i,0,m){
		ls0[i]=ls[i];
		if(rev[i])ls0[i].a*=-1,ls0[i].b*=-1,ls0[i].c*=-1;
	}
	
	sort(ls,ls+m);
	F(i,0,m)pos[ls[i].id]=i;
	F(i,0,m)pos0[i]=pos[i];
	
	cp=0;
	F(i,0,m)F(j,0,i)cp+=cs[cp].init(ls[i],ls[j],i*B+j);
	
	sort(cs,cs+cp);
	
	np=0;np2=m+1;
	F(i,0,m){
		n1[i]=n0[i]=ns+np;
		ns[np++].init(i);
	}
	F(i,0,np2)ns2[i].init();
	int p=0;
	for(int i=0;;++i){
		for(;p<n&&(i==cp||ps[p]<cs[i]);++p){
			cur_x=ps[p].x;
			Line w{0,1,ps[p].y,0};
			int p1=std::lower_bound(ls,ls+m,w,Cmp())-ls,ans;
			if(p1==m)ans=n0[m-1]->d;
			else ans=n0[p1]->u;
			ns2[ans].init(ps[p]);
		}
		if(i==cp)break;
		int id1=cs[i].w1;
		int id2=cs[i].w2;
		int &p1=pos[id1];
		int &p2=pos[id2];
		
		assert(std::abs(p1-p2)==1);
		swap(ls[p1],ls[p2]);
		
		node *w1=n0[p1],*w2=n0[p2];
		node *w3=ns+np++;
		node *w4=ns+np++;
		w3->lk(w1,w4);
		w4->lk(w2,w3);
		n0[p1]=w4;
		n0[p2]=w3;
		if(w1->d!=w2->u)swap(w1,w2),swap(w3,w4);
		w4->u=w1->u;
		w3->d=w2->d;
		ns2[np2].init();
		w4->d=w3->u=np2++;
		
		swap(p1,p2);
	}
	using namespace KDT;
	Np=Ns;
	for(int i=0;i<np2;++i){
		if(ns2[i].p0.d.empty())continue;
		Np->init(ns2[i].p0);
		Np->src=ns2+i;
		++Np;
	}
	Node *Np0=Np;
	Rt=build(Ns,Np);
	for(int i=0;i<m;++i){
		Data ans;
		ans.clr();
		Rt->op(ls0[i]);
		Rt->op(ms[i],ans);
		ans.print();
	}
	Rt->dna();
	for(Node* p=Ns;p<Np0;++p)p->src->t=p->t;
	
	F(i,0,n)ps[i].t->apply(ps[i].d);
}
void solve(
	const int n,
	const int m,
	const int *x,
	const int *y,
	const Data *d,
	const int *a,
	const int *bs,
	const int *c,
	const Operation *o){
	::n=n;
	F(i,0,n)ps[i].init(x[i],y[i],d[i]);
	sort(ps,ps+n);
	::q=m;
	
	int B=(int)cbrt(n*2/3)+1;
	//fprintf(stderr,">>> %d\n",2*n*(q/B+1)+3*q*(B*(B+1)/2+1));
	int i0=0;
	while(q>0){
		int b=std::min(q,B);
		F(i,0,b){
			ls[i].init(a[i0],bs[i0],c[i0],i);
			ms[i]=o[i0++];
		}
		calc(b);
		q-=b;
	}
}