QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#740079#9020. 测测你的半平面修改查询I_be_wanna100 ✓1017ms48240kbC++2036.3kb2024-11-13 00:55:212024-11-13 00:55:22

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 00:55:22]
  • 评测
  • 测评结果:100
  • 用时:1017ms
  • 内存:48240kb
  • [2024-11-13 00:55:21]
  • 提交

answer

#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];
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];
void merge(int x,int y);
void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}
void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}
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 DSU{
	int f,v;
}dsu[B*B];
struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;
struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;
void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};
int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}
void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}
void calc(int m){
	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);
	}
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
	}
	{Undo _;dc(0,m);}
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	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;
	}
}

/*#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];

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];

void merge(int x,int y);

void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}

void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}

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 DSU{
	int f,v;
}dsu[B*B];

struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;

struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;

void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};

int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}

void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}

void calc(int m){
	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);
	}
	//int zs=0;
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
		//if(ns2[i].d.empty())++zs;
	}
	//fprintf(stderr,"%d/%d\n",zs,np2);
	
	{Undo _;dc(0,m);}
	
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	//for(int i=0;i<6;++i)s=std::min(s,(n<<i)+(B*B>>i));
	//fprintf(stderr,">>> %d %d %d\n",k*s,k*s,k*(s-n));
	//fprintf(stderr,">>> %d\n",k*s+k*s+k*(s-n));
	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;
	}
}#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];

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];

void merge(int x,int y);

void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}

void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}

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 DSU{
	int f,v;
}dsu[B*B];

struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;

struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;

void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};

int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}

void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}

void calc(int m){
	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);
	}
	//int zs=0;
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
		//if(ns2[i].d.empty())++zs;
	}
	//fprintf(stderr,"%d/%d\n",zs,np2);
	
	{Undo _;dc(0,m);}
	
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	//for(int i=0;i<6;++i)s=std::min(s,(n<<i)+(B*B>>i));
	//fprintf(stderr,">>> %d %d %d\n",k*s,k*s,k*(s-n));
	//fprintf(stderr,">>> %d\n",k*s+k*s+k*(s-n));
	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;
	}
}#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];

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];

void merge(int x,int y);

void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}

void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}

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 DSU{
	int f,v;
}dsu[B*B];

struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;

struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;

void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};

int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}

void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}

void calc(int m){
	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);
	}
	//int zs=0;
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
		//if(ns2[i].d.empty())++zs;
	}
	//fprintf(stderr,"%d/%d\n",zs,np2);
	
	{Undo _;dc(0,m);}
	
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	//for(int i=0;i<6;++i)s=std::min(s,(n<<i)+(B*B>>i));
	//fprintf(stderr,">>> %d %d %d\n",k*s,k*s,k*(s-n));
	//fprintf(stderr,">>> %d\n",k*s+k*s+k*(s-n));
	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;
	}
}#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];

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];

void merge(int x,int y);

void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}

void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}

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 DSU{
	int f,v;
}dsu[B*B];

struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;

struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;

void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};

int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}

void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}

void calc(int m){
	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);
	}
	//int zs=0;
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
		//if(ns2[i].d.empty())++zs;
	}
	//fprintf(stderr,"%d/%d\n",zs,np2);
	
	{Undo _;dc(0,m);}
	
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	//for(int i=0;i<6;++i)s=std::min(s,(n<<i)+(B*B>>i));
	//fprintf(stderr,">>> %d %d %d\n",k*s,k*s,k*(s-n));
	//fprintf(stderr,">>> %d\n",k*s+k*s+k*(s-n));
	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;
	}
}#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];

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];

void merge(int x,int y);

void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}

void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}

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 DSU{
	int f,v;
}dsu[B*B];

struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;

struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;

void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};

int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}

void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}

void calc(int m){
	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);
	}
	//int zs=0;
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
		//if(ns2[i].d.empty())++zs;
	}
	//fprintf(stderr,"%d/%d\n",zs,np2);
	
	{Undo _;dc(0,m);}
	
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	//for(int i=0;i<6;++i)s=std::min(s,(n<<i)+(B*B>>i));
	//fprintf(stderr,">>> %d %d %d\n",k*s,k*s,k*(s-n));
	//fprintf(stderr,">>> %d\n",k*s+k*s+k*(s-n));
	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;
	}
}#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];

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];

void merge(int x,int y);

void del(int L,int R){
	F(i,L,R){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			merge(w->u,w->d);
			node *u=w->p;
			if(u){
				node *v=u->l->r=u->r;
				if(v)v->l=u->l;
			}
		}
	}
}

void ins(int L,int R){
	for(int i=R-1;i>=L;--i){
		node *w=n1[pos0[i]];
		for(;w;w=w->r){
			node *u=w->p;
			if(u){
				u->l->r=u;
				node *v=u->r;
				if(v)v->l=u;
			}
		}
	}
}

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 DSU{
	int f,v;
}dsu[B*B];

struct node2;
node2*d_useful;
struct node2{
	node2*lc,*rc;
	Data d;
	Operation t;
	void init(){
		lc=rc=0;
		d.clr();
		t.clr();
	}
	void init(Pos &p){
		d.add_eq(p.d);
		p.t=&t;
	}
	void init(node2*l,node2*r){
		lc=l;rc=r;
		d.add(l->d,r->d);
		t.clr();
	}
	void apply(const Operation &w){
		if(d.empty())return;
		w.apply(t);
		if(this<d_useful)w.apply(d);
	}
	void destroy()const{
		lc->apply(t);
		rc->apply(t);
	}
}ns2[B*B*2];
int np2;

struct Op{
	int *x,y;
	void undo(){*x=y;}
}ops[B*B*3];
int opp=0;

void _set(int &x,int y){
	ops[opp++]=Op{&x,x};
	x=y;
}
struct Undo{
	int p,p2;
	Undo():p(opp),p2(np2){}
	~Undo(){
		d_useful=ns2+p2;
		while(np2>p2)ns2[--np2].destroy();
		while(opp>p)ops[--opp].undo();
	}
};

int find(int x){
	while(dsu[x].f>=0)x=dsu[x].f;
	return x;
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	assert(x!=y);
	int &nx=dsu[x].v,&ny=dsu[y].v;
	ns2[np2].init(ns2+nx,ns2+ny);
	int &hx=dsu[x].f,&hy=dsu[y].f;
	if(hx==hy)_set(hx,y),_set(hy,hy-1),_set(ny,np2);
	else if(hx>hy)_set(hx,y),_set(ny,np2);
	else _set(hy,x),_set(nx,np2);
	++np2;
}

void dc(int L,int R){
	if(R-L==1){
		bool tp=rev[L];
		int id=find(tp?n1[pos0[L]]->d:n1[pos0[L]]->u);
		id=dsu[id].v;
		d_useful=ns2+np2;
		ns2[id].d.print();
		ns2[id].apply(ms[L]);
		return;
	}
	int M=(L+R)>>1;
	{Undo _;del(M,R);dc(L,M);ins(M,R);}
	del(L,M);dc(M,R);ins(L,M);
}

void calc(int m){
	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);
	}
	//int zs=0;
	F(i,0,np2){
		dsu[i]=DSU{-1,i};
		//if(ns2[i].d.empty())++zs;
	}
	//fprintf(stderr,"%d/%d\n",zs,np2);
	
	{Undo _;dc(0,m);}
	
	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)sqrt(n*2/3)+1;
	B=std::min(B,q);
	int s=n+B*B,k=(q+B-1)/B;
	//for(int i=0;i<6;++i)s=std::min(s,(n<<i)+(B*B>>i));
	//fprintf(stderr,">>> %d %d %d\n",k*s,k*s,k*(s-n));
	//fprintf(stderr,">>> %d\n",k*s+k*s+k*(s-n));
	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;
	}
}*/

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 25ms
memory: 20820kb

input:

20000
5245 -9733 6
2898 -2273 6
-3025 13598 7
-2111 542 3
-913 -1516 6
-1525 -1050 2
17646 4583 6
-2101 -1295 10
-635 1367 4
-2828 1004 6
-1497 -2603 5
-3415 -3290 7
3995 -6478 2
-2093 -203 6
2748 181 9
-9456 206 6
-15645 14633 9
-4783 555 3
-4383 425 5
-20919 36410 1
1921 -405 1
3934 8809 4
-1303 -...

output:

628859
1184568235

result:

ok The answer is correct.

Test #2:

score: 5
Accepted
time: 22ms
memory: 18988kb

input:

20000
686 -1046 4
694 850 10
-830 -8542 1
-795 1008 7
12881 -3183 1
961 -394 1
-1031 -259 2
8442 -2883 7
-14 -1204 1
1121 418 1
1102 -453 9
-574 -827 5
4775 -1978 7
1006 2061 5
3575 1146 7
-546 -934 6
1037 -159 1
-965 -304 2
-878 -573 5
345 1893 6
-1080 5502 3
-294 1155 10
1789 -2 5
217 1179 6
911 -...

output:

648690
1565105122

result:

ok The answer is correct.

Test #3:

score: 5
Accepted
time: 29ms
memory: 20600kb

input:

20000
11122 -11638 4
-1740 -5825 9
-3944 2250 8
1964 983 2
-4102 2439 2
11896 -2032 4
-6247 -3805 8
-875 -2529 10
81 4894 5
-2103 -227 7
1819 2958 2
2822 5467 2
5556 -8941 6
11961 7486 6
-1291 -2731 2
20342 -1088 1
194 3036 10
-6729 5391 1
1164 1694 10
-34776 -45966 3
622 -2586 6
1607 -4155 6
-22275...

output:

631949
3203875655

result:

ok The answer is correct.

Test #4:

score: 5
Accepted
time: 28ms
memory: 24924kb

input:

20000
438860 -73910 1
228935 75600 4
-961920 188700 8
660015 655330 6
-18922 196153 2
-855750 819770 5
40151 -175778 4
145568 92246 3
512816 147766 2
207512 182989 9
134174 31956 10
178622 -186978 6
-343680 100680 6
115980 305670 8
-174382 307699 9
478417 373980 2
-201400 -102780 5
-71050 -612550 3
...

output:

603045
2618948775

result:

ok The answer is correct.

Test #5:

score: 5
Accepted
time: 15ms
memory: 18580kb

input:

20000
398519 123762 8
-571339 -86531 4
-241091 447702 5
-96819 557807 1
124523 -180638 10
420494 -575313 5
-589407 278420 8
-805008 -160484 7
-231491 -328375 1
283671 -132403 8
285203 612859 7
-354672 -47543 4
624976 40852 7
-386647 -33515 9
-122556 389227 8
535015 -282411 5
-16618 -949802 10
-74675...

output:

531318
2246548101

result:

ok The answer is correct.

Test #6:

score: 5
Accepted
time: 29ms
memory: 24868kb

input:

20000
6889 -29721 8
-1036 12027 6
10547 -290 8
-10371 -677 8
-3756 898 3
4874 -2930 5
-7515 6173 8
12336 1374 10
174220 -173020 8
4985 -1557 10
3230 10378 8
-9111 -4121 10
10509 -534 8
-11098 -2764 6
-44859 -51666 4
188 -13280 2
-8390 5440 5
-5333 -11150 2
3908 -17979 1
-7398 -17442 9
16424 3525 5
2...

output:

604896
389229703

result:

ok The answer is correct.

Test #7:

score: 5
Accepted
time: 26ms
memory: 18964kb

input:

20000
1633 259 5
579 -1029 1
498 1139 7
171 474 6
675 -85 8
371 -52 9
-2073 2829 8
-5 -1111 10
-795 195 9
-11 144 8
-238 41 1
405 614 3
128 410 10
-324 -1193 8
-4317 7438 2
-236 300 5
420 -629 2
509 637 4
-436 228 5
-246 581 2
189 1385 2
1363 1816 5
553 -344 6
-148 -108 1
190 450 5
659 -1115 4
202 -...

output:

613908
2817220556

result:

ok The answer is correct.

Test #8:

score: 5
Accepted
time: 19ms
memory: 18876kb

input:

20000
0 -1 2
0 7 1
-998285 499142 9
209116 418238 2
91751 -183498 5
-4 -2 8
-2 -2 7
5 -1 2
-1 -3 1
-5 6 9
-34226 68447 8
-810116 -405054 1
80050 -160092 1
1 -2 7
1 -5 10
0 4 4
-7 -1 1
3 1 9
-1 7 2
2 -2 1
-123822 247644 10
-3 -2 4
-5 -4 7
-6 8 8
157702 -315413 9
2 -1 5
-4 0 10
3 0 10
-205546 -411093 ...

output:

482213
905897730

result:

ok The answer is correct.

Test #9:

score: 5
Accepted
time: 18ms
memory: 22952kb

input:

20000
-478255 358690 10
-1 2 7
306414 -153207 2
-1 3 5
-313442 -313441 5
204483 -102240 10
-2 -2 6
-851493 -425749 3
-53735 161214 5
302522 -453784 6
-303898 -151948 2
5 -3 6
-55683 83527 10
-302149 453227 7
-104583 -104585 8
-115225 172834 5
2 0 2
108784 81588 3
14 5 6
146710 97808 8
73175 48782 1
...

output:

531223
1748878069

result:

ok The answer is correct.

Test #10:

score: 5
Accepted
time: 9ms
memory: 20584kb

input:

20000
-999566 -999553 7
-998415 -998413 9
-999637 -999642 4
-999533 -999541 6
-999217 -999213 9
-998699 -998689 6
-998866 -998859 3
-999344 -999343 2
-999057 -999048 1
-999927 -999932 6
-999270 -999270 9
-999063 -999065 9
-998815 -998804 4
-998534 -998545 7
-999423 -999431 10
-999510 -999503 1
-9991...

output:

427392
795812623

result:

ok The answer is correct.

Test #11:

score: 5
Accepted
time: 11ms
memory: 24376kb

input:

20000
-999587 -999588 8
-998343 -998350 6
-999715 -999715 4
-999162 -999156 2
-998649 -998641 4
-998063 -998061 10
-997911 -997919 5
-998540 -998541 10
-998798 -998786 6
-998314 -998318 10
-998657 -998657 6
-998880 -998870 4
-998577 -998568 2
-998593 -998593 5
-999079 -999084 2
-997241 -997245 6
-99...

output:

422356
1011088017

result:

ok The answer is correct.

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #12:

score: 15
Accepted
time: 25ms
memory: 23012kb

input:

20000
2641 1830 6
-2037 -206 1
-6986 489 3
-3427 3874 9
-810 -5729 8
-48 -797 3
3035 1378 1
9159 -7860 2
-3123 -7198 6
2024 -417 4
3348 -7912 7
1093 1896 1
2878 2836 1
906 1826 3
-1728 2809 10
-12842 5268 7
2552 -225 8
20452 22770 5
2793 2016 10
-1624 592 4
-1838 6563 7
-4113 2448 4
4533 -2058 8
121...

output:

628749
2203490789

result:

ok The answer is correct.

Test #13:

score: 15
Accepted
time: 27ms
memory: 24772kb

input:

20000
1293 -799 4
421 925 3
-128 -1838 4
-530 940 7
-1372 -1831 4
990 1769 10
941 1712 9
702 732 3
-1309 31 2
-722 -883 2
-1413 429 10
3260 1227 4
-359 1208 10
-1262 -1302 2
-1651 -432 8
-2932 -1837 2
984 893 1
9 -1313 6
463 -887 9
-1052 2904 6
13076 19590 2
73 -1022 8
948 -1023 3
-976 -220 1
909 51...

output:

649785
2272327052

result:

ok The answer is correct.

Test #14:

score: 15
Accepted
time: 24ms
memory: 18684kb

input:

20000
282847 -295662 7
1601 -1204 4
-552 3120 4
8775 7941 9
16268 -19275 2
-28819 -25979 9
18994 5034 7
-651 5382 6
26284 -8042 8
269 1358 10
8779 13531 4
5319 -22 7
-10061 -636 4
5954 -23095 10
1344 2377 4
314000 -309000 2
3016 -2655 10
13615 -121209 10
-16480 -7830 6
-4287 -3794 3
5903 -3943 3
-89...

output:

631060
889942214

result:

ok The answer is correct.

Test #15:

score: 15
Accepted
time: 19ms
memory: 20964kb

input:

20000
135586 35657 5
180026 157525 6
449471 223328 4
124474 172377 9
-166933 -759713 1
906838 -11616 1
-165705 35036 1
-712882 -219928 8
178708 43082 1
221322 214935 10
-98520 18910 5
-153292 -162598 9
-18968 46590 7
96560 -21437 5
-100470 50686 3
-37150 766920 7
-412972 -19568 7
-3978 -120613 2
103...

output:

605424
418557609

result:

ok The answer is correct.

Test #16:

score: 15
Accepted
time: 18ms
memory: 18656kb

input:

20000
-553604 420694 6
55113 -286634 4
-387689 511617 2
26205 -31833 4
470111 476524 2
-359016 -520263 2
719986 -133408 3
493237 -179036 7
-184451 -636874 2
-288831 11296 1
332922 37952 7
-113180 -244261 8
-303632 -511096 4
-405386 -73568 6
379774 438503 9
-182392 209023 10
347793 -5426 10
896165 61...

output:

533683
1261937652

result:

ok The answer is correct.

Test #17:

score: 15
Accepted
time: 24ms
memory: 18852kb

input:

20000
4040 -19449 8
-1455 -9893 6
7007 -18256 2
6069 -19060 9
78528 75381 1
-6571 7552 3
5612 -8791 9
10499 -537 9
452 -13852 3
-5028 5827 3
4461 -7472 2
5614 -7638 7
-1006 -4627 9
-1363 -9671 8
3405 -5916 1
-3726 -6121 9
-6478 -3298 3
21122 21138 9
4922 6958 9
43728 70110 10
90437 -78593 2
174637 9...

output:

606748
3139127476

result:

ok The answer is correct.

Test #18:

score: 15
Accepted
time: 19ms
memory: 26704kb

input:

20000
1241 1555 9
399 20 3
-4382 -2258 4
1774 -137 2
-85 -814 1
-1042 -1130 5
-682 -618 10
-158 135 1
395 244 4
1578 1345 3
-43 846 9
-3620 -723 6
-1491 -933 10
2370 3298 3
-1 -224 3
-1129 -560 2
2228 -2775 5
667 -856 5
-494 -157 2
731 -139 5
-546 -710 1
-2480 454 3
354 -1011 10
-186 80 7
-202 56 4
...

output:

612627
1341688909

result:

ok The answer is correct.

Test #19:

score: 15
Accepted
time: 19ms
memory: 18728kb

input:

20000
0 -4 2
5 0 3
-2 -2 9
788653 -394326 1
5 -7 3
434528 -217261 9
213237 -426467 10
0 4 10
136812 273628 10
126407 -252807 7
6 3 9
133608 267213 10
0 6 6
-140140 280285 4
-3 -3 9
0 3 6
-67955 -33975 2
-1 5 5
1 5 6
2 1 6
-1 2 1
917426 -458710 10
-41577 83147 10
-201684 -403364 2
1 2 3
-151147 -7557...

output:

481447
3707819941

result:

ok The answer is correct.

Test #20:

score: 15
Accepted
time: 17ms
memory: 20772kb

input:

20000
405164 -405164 7
3 1 6
-44158 88313 3
-323949 215966 7
-730999 -243667 6
2 0 10
248596 -165733 3
-99114 74337 4
-2 2 6
-766127 -191531 4
-543887 -407914 4
-3 4 3
-248432 248429 7
-286491 190996 9
-9 0 5
147986 147987 3
0 -1 4
286412 286416 10
-13214 -13211 9
0 3 1
3 0 4
-322175 -322174 4
1 -2 ...

output:

529404
3951658115

result:

ok The answer is correct.

Test #21:

score: 15
Accepted
time: 11ms
memory: 22488kb

input:

20000
-998437 -998440 7
-998615 -998622 3
-999647 -999660 9
-999740 -999735 6
-998790 -998790 9
-999916 -999923 10
-999760 -999754 9
-999291 -999303 3
-999101 -999115 1
-998770 -998766 3
-999329 -999326 2
-999651 -999657 8
-999480 -999470 3
-998962 -998973 7
-999677 -999672 1
-999949 -999953 7
-9999...

output:

428095
3534086169

result:

ok The answer is correct.

Test #22:

score: 15
Accepted
time: 7ms
memory: 18568kb

input:

20000
-998773 -998774 6
-998426 -998423 8
-997858 -997853 8
-998302 -998311 2
-998788 -998793 10
-998254 -998255 10
-998926 -998930 9
-998263 -998270 8
-998514 -998500 5
-998859 -998865 4
-997894 -997885 2
-997695 -997694 4
-999438 -999435 2
-998993 -998992 8
-998809 -998811 4
-996275 -996276 8
-996...

output:

427126
2769937809

result:

ok The answer is correct.

Subtask #3:

score: 5
Accepted

Test #23:

score: 5
Accepted
time: 32ms
memory: 31084kb

input:

200000
-1014 -2657 4
-441 -2850 9
-860 3331 8
6027 -6526 6
144250 69365 6
-2855 -3780 9
1460 2333 6
-644 1051 10
-4535 -3692 1
3573 -175 4
232 2495 5
-3996 2251 7
6945 -17184 8
-9520 1403 1
2112 1387 8
-1205 1496 8
2673 605 10
-2820 -973 3
558 -846 2
-17020 -11100 7
868 2321 8
-580 -758 6
1785 -1253...

output:

431606
1475663463

result:

ok The answer is correct.

Test #24:

score: 5
Accepted
time: 27ms
memory: 29392kb

input:

200000
31593 29215 4
3175 -2692 10
1876 792 7
3241 797 5
-4043 12516 9
-1807 971 7
1397 -993 10
367 1284 7
175 -1027 3
-571 2811 4
-2337 978 10
-7393 40407 8
1008 -1394 6
700 -745 4
220 1192 1
3314 119 8
1049 177 1
-848 2561 8
-3393 486 1
1037 242 5
-2506 4006 10
1088 -1076 3
3576 392 3
-5294 -7256 ...

output:

432599
1700331537

result:

ok The answer is correct.

Test #25:

score: 5
Accepted
time: 25ms
memory: 30108kb

input:

200000
7482 10251 7
-674 -3115 8
-12482 29166 2
3410 5181 6
2023 -111 9
-3389 1076 6
-665 -4545 2
-128926 179024 5
-36372 22327 3
20097 2525 9
846 7500 3
2292 -9338 1
-1763 -1802 8
1416 -1420 7
129787 17300 10
1767 977 1
-5978 -1291 2
36388 8452 9
-4025 770 2
7456 4224 8
2213 -3648 5
9902 -22535 6
-...

output:

431905
4285388758

result:

ok The answer is correct.

Test #26:

score: 5
Accepted
time: 22ms
memory: 32044kb

input:

200000
696558 56906 5
-299486 80870 8
172464 -271336 7
-178465 42958 1
135682 42372 9
45648 -189508 5
242480 101920 6
441790 191460 3
57110 14232 8
72596 499038 7
-160421 165248 6
-101042 136546 10
79616 -210804 4
74530 140360 2
-273490 111650 2
52294 163321 5
44880 247930 6
-219946 -13062 8
-205985...

output:

427998
4007150453

result:

ok The answer is correct.

Test #27:

score: 5
Accepted
time: 31ms
memory: 29620kb

input:

200000
-181659 -392133 2
682822 -165783 3
-150583 -330974 4
86298 299407 6
532528 214452 2
-45743 -35689 2
-53974 459595 1
193386 91173 6
-156137 671316 1
114443 -76044 4
331684 -611676 8
-388788 466140 3
224209 650199 3
-39516 640868 2
36464 650059 3
-34812 490820 3
38927 -69366 7
348395 -451516 3
...

output:

418285
395174535

result:

ok The answer is correct.

Test #28:

score: 5
Accepted
time: 25ms
memory: 30208kb

input:

200000
2484 8786 7
-3420 -27610 8
-1367 4564 7
-9111 -4121 6
4283 -4065 6
6253 -5375 3
3310 -5763 8
4760 -8098 7
-6381 5886 1
-11724 -3846 2
5087 -3417 2
-7779 7240 4
-861 -14238 4
6165 -4350 9
-4997 489 5
-5960 -12091 5
-1031 -9170 10
1365 21322 9
-3752 -6737 1
-513980 -601268 6
-23185 18459 3
8536...

output:

428869
1650421457

result:

ok The answer is correct.

Test #29:

score: 5
Accepted
time: 26ms
memory: 27724kb

input:

200000
1537 1501 8
-117 -126 1
685 235 9
546 256 6
944 -347 3
624 890 3
362 2015 5
-2439 -200 2
-843 -630 1
149 356 9
-885 -688 3
-1851 2126 2
404 -934 8
290 -1574 3
311 -66 1
-1225 780 9
-36 624 3
260 -548 3
498 -152 2
72 -916 2
-395 -13 2
29 640 6
617 11 7
-423 -282 7
-734 -685 3
433 911 10
86 199...

output:

429284
3400699918

result:

ok The answer is correct.

Test #30:

score: 5
Accepted
time: 23ms
memory: 29532kb

input:

200000
2 3 2
-2 2 7
1 5 1
-3 2 6
2 0 5
37797 -75592 6
2 2 2
2 1 4
-6 -5 10
-356480 178236 7
197841 395680 9
-1 0 10
183874 367748 7
-309466 154735 10
0 1 10
5 3 3
388611 194301 2
1 -2 3
-4 1 4
0 0 2
127035 -254066 4
-44451 88897 1
-1 2 2
1 -3 4
53370 -106742 2
-3 1 2
642925 -321465 2
5 -4 5
151369 -...

output:

412137
2696913447

result:

ok The answer is correct.

Test #31:

score: 5
Accepted
time: 28ms
memory: 29308kb

input:

200000
15 -25 8
8 0 2
-3 0 10
344864 114958 4
-774946 387474 1
2 1 10
822507 411257 10
-1 0 4
-148954 -446867 5
-2 -4 5
-584095 292048 6
0 0 6
-118521 -237039 1
-3 1 5
-2 0 10
211814 211815 10
-45540 -22767 8
-205809 205813 3
3 3 3
982179 -245547 3
19708 39407 3
-6 -7 7
-635704 317849 8
171184 17118...

output:

416188
4028719501

result:

ok The answer is correct.

Test #32:

score: 5
Accepted
time: 23ms
memory: 30952kb

input:

200000
-999668 -999663 3
-999726 -999720 2
-999899 -999894 8
-999970 -999961 10
-999787 -999787 5
-999723 -999717 10
-999739 -999736 2
-999678 -999671 9
-999932 -999938 7
-999691 -999680 7
-999827 -999827 3
-999768 -999768 6
-999963 -999963 5
-999756 -999751 7
-999813 -999804 4
-999760 -999755 3
-99...

output:

406283
4149368756

result:

ok The answer is correct.

Test #33:

score: 5
Accepted
time: 14ms
memory: 28696kb

input:

200000
-999927 -999923 4
-999825 -999829 9
-999994 -999984 8
-999833 -999833 2
-999943 -999938 2
-999689 -999687 7
-999922 -999916 2
-999736 -999720 1
-999845 -999859 4
-999854 -999858 3
-999871 -999876 7
-999775 -999782 7
-999667 -999671 9
-999830 -999823 5
-999832 -999830 10
-999785 -999781 5
-999...

output:

406092
2525605831

result:

ok The answer is correct.

Subtask #4:

score: 15
Accepted

Dependency #3:

100%
Accepted

Test #34:

score: 15
Accepted
time: 23ms
memory: 31080kb

input:

200000
-1674 -832 7
-3834 -6457 5
-139143 -294548 1
7100 -8777 3
1687 -1816 7
3267 -3450 5
-7284 -2796 5
-2341 -1343 9
1509 -567 5
-715 -3898 7
-82 818 9
7398 -18124 4
1405 3516 9
815 1567 5
6627 3543 7
7767 15939 3
-1029 -99 2
42 931 1
2135 -1482 1
-2848 -1015 2
3665 1813 2
-2091 -1908 9
49 1263 9
...

output:

431596
3288359239

result:

ok The answer is correct.

Test #35:

score: 15
Accepted
time: 30ms
memory: 30960kb

input:

200000
1931 1008 4
17736 -10372 5
1045 -415 7
-123 1022 2
-1103 -347 9
-857 -564 9
-892 -494 9
915 2536 1
930 734 4
-1021 1166 6
392 -1141 8
-947 460 2
942 -402 1
3274 -5902 2
669 -918 2
864 509 7
1056 367 7
-376 1062 9
6608 4986 4
-1089 -182 10
-2068 -1153 5
-1067 -1556 5
292 1095 7
-3729 436 6
281...

output:

433309
3492291470

result:

ok The answer is correct.

Test #36:

score: 15
Accepted
time: 27ms
memory: 28904kb

input:

200000
-5621 9153 7
3127 -6722 6
118 1381 2
-2020 -704 2
2982 8143 5
648 -4953 2
-7951 -4988 3
553 1933 2
2341 11191 8
-6780 -8753 5
-254 6531 7
3147 -1065 5
-16628 -1069 8
1950 -539 6
98179 -26114 5
-1999 -1062 5
-14596 14346 4
-1265 -151 7
7967 -6181 8
-1013 1118 10
-1946 3960 10
-1721 -3000 4
-22...

output:

431686
1868830709

result:

ok The answer is correct.

Test #37:

score: 15
Accepted
time: 26ms
memory: 29924kb

input:

200000
-525325 665225 10
-262512 198085 9
-209457 193860 2
690080 -456008 8
-186746 -2766 1
-30004 169133 2
-64912 72465 1
-167600 371130 4
-93629 -159267 6
22257 107525 7
-19655 99940 10
-168790 -31741 2
-26062 -121367 9
16547 -128110 9
-113505 46055 1
-720677 -163328 9
329444 -122273 9
194032 1313...

output:

427900
2250220609

result:

ok The answer is correct.

Test #38:

score: 15
Accepted
time: 27ms
memory: 28900kb

input:

200000
817531 147545 2
-921621 44948 4
-89498 82295 3
46093 939349 8
322801 -380412 7
278926 454245 4
-209620 -3238 2
325161 305649 8
404511 -360449 10
-612653 -207622 9
-474893 -220870 4
472828 -322112 6
-54213 179580 6
-642401 -245004 4
-32156 -67735 4
-92357 -464176 1
-205042 -505877 1
-41734 408...

output:

418072
2368005640

result:

ok The answer is correct.

Test #39:

score: 15
Accepted
time: 28ms
memory: 31808kb

input:

200000
16891 -2286 1
-160264 -95389 4
-1560 -10082 9
-9125 8639 9
11881 28972 8
-9111 -4121 1
-56469 -24696 8
-5137 -48142 6
9417 -15399 4
46300 -36803 7
31772 -3958 3
3410 8932 2
11762 -2723 4
-3043 7127 5
9876 2097 9
-3257 -1325 5
-8390 5440 5
-6103 -12869 6
-14805 -84 10
3200 -17468 7
-2606 -1665...

output:

429379
358490033

result:

ok The answer is correct.

Test #40:

score: 15
Accepted
time: 21ms
memory: 29924kb

input:

200000
1097 -115 5
-1013 1381 8
-1842 2090 3
1527 -3651 1
-1836 -719 6
-275 -215 8
-36 -765 8
226 -24 9
1719 -2181 4
5358 -8811 6
-605 1807 6
-1561 303 2
977 462 9
-1238 -178 6
-671 95 8
-1051 40 2
-1492 -1882 10
-2299 -76 2
245 -402 1
3567 8845 2
-78 1059 8
1291 5078 5
-106 -415 2
454 503 2
332 -58...

output:

429728
1659682910

result:

ok The answer is correct.

Test #41:

score: 15
Accepted
time: 28ms
memory: 29224kb

input:

200000
0 3 2
2 2 6
-2 0 5
-1 -1 9
0 -2 8
15197 30399 10
111350 -222692 4
793088 396543 3
0 0 9
5 0 10
-8 0 5
1 1 4
7 -1 1
2 -5 1
11542 -23092 6
0 1 6
-6 0 5
-1 1 1
8 9 6
-4 0 7
-18257 -9133 10
95376 -190749 9
-215244 430499 9
-1 4 4
-6 3 6
-5 6 6
2 0 3
-676042 -338020 6
-732236 -366119 3
248616 4972...

output:

412335
1275547843

result:

ok The answer is correct.

Test #42:

score: 15
Accepted
time: 28ms
memory: 30140kb

input:

200000
-143483 -107614 2
-674481 449657 4
-19 16 8
-4 0 9
-2 2 8
-293107 146552 4
386411 193204 1
384639 256428 6
-1 -3 1
5 -4 1
395740 -263828 6
207573 -415142 7
652851 -217620 7
-992583 -496291 1
-3 -1 7
258083 258085 8
14 -37 4
147947 -49316 4
606546 404362 4
255842 -191883 2
-20 15 2
14488 14488...

output:

418307
4069995663

result:

ok The answer is correct.

Test #43:

score: 15
Accepted
time: 17ms
memory: 29640kb

input:

200000
-999663 -999679 1
-999755 -999749 1
-999678 -999666 7
-999735 -999739 4
-999907 -999910 10
-999751 -999739 6
-999738 -999736 9
-999948 -999941 2
-999726 -999729 5
-999696 -999706 5
-999640 -999650 6
-999749 -999763 7
-999710 -999695 9
-999795 -999786 1
-999921 -999915 1
-999857 -999852 9
-999...

output:

405502
1102507425

result:

ok The answer is correct.

Test #44:

score: 15
Accepted
time: 17ms
memory: 34828kb

input:

200000
-999798 -999799 6
-999632 -999640 3
-999738 -999734 7
-999649 -999648 2
-999862 -999857 4
-999640 -999641 2
-999752 -999753 6
-999927 -999934 2
-999732 -999731 2
-999694 -999697 4
-999892 -999878 10
-999940 -999930 1
-999854 -999858 10
-999631 -999624 1
-999943 -999945 5
-999720 -999736 3
-99...

output:

405826
3656377611

result:

ok The answer is correct.

Subtask #5:

score: 20
Accepted

Test #45:

score: 20
Accepted
time: 318ms
memory: 28048kb

input:

65536
-128 -128 6
-128 -127 3
-128 -126 3
-128 -125 2
-128 -124 8
-128 -123 8
-128 -122 6
-128 -121 3
-128 -120 10
-128 -119 2
-128 -118 6
-128 -117 9
-128 -116 7
-128 -115 1
-128 -114 8
-128 -113 3
-128 -112 4
-128 -111 6
-128 -110 9
-128 -109 10
-128 -108 6
-128 -107 7
-128 -106 9
-128 -105 3
-128...

output:

9041653
1531224321

result:

ok The answer is correct.

Test #46:

score: 20
Accepted
time: 324ms
memory: 23884kb

input:

65536
-128 -128 1
-128 -127 7
-128 -126 4
-128 -125 9
-128 -124 3
-128 -123 6
-128 -122 8
-128 -121 10
-128 -120 3
-128 -119 6
-128 -118 10
-128 -117 8
-128 -116 10
-128 -115 3
-128 -114 6
-128 -113 8
-128 -112 9
-128 -111 6
-128 -110 2
-128 -109 8
-128 -108 4
-128 -107 9
-128 -106 8
-128 -105 4
-12...

output:

9035634
272259564

result:

ok The answer is correct.

Test #47:

score: 20
Accepted
time: 183ms
memory: 23680kb

input:

65536
-128 -128 10
-128 -127 7
-128 -126 5
-128 -125 7
-128 -124 10
-128 -123 4
-128 -122 10
-128 -121 10
-128 -120 1
-128 -119 5
-128 -118 9
-128 -117 8
-128 -116 6
-128 -115 7
-128 -114 3
-128 -113 2
-128 -112 10
-128 -111 3
-128 -110 4
-128 -109 6
-128 -108 9
-128 -107 1
-128 -106 8
-128 -105 1
-...

output:

6999710
3364760732

result:

ok The answer is correct.

Test #48:

score: 20
Accepted
time: 183ms
memory: 27276kb

input:

65536
-128 -128 6
-128 -127 10
-128 -126 8
-128 -125 3
-128 -124 6
-128 -123 1
-128 -122 9
-128 -121 3
-128 -120 4
-128 -119 1
-128 -118 6
-128 -117 4
-128 -116 4
-128 -115 1
-128 -114 10
-128 -113 3
-128 -112 8
-128 -111 10
-128 -110 10
-128 -109 2
-128 -108 3
-128 -107 8
-128 -106 9
-128 -105 10
-...

output:

6986921
4169494042

result:

ok The answer is correct.

Subtask #6:

score: 10
Accepted

Test #49:

score: 10
Accepted
time: 117ms
memory: 29684kb

input:

200000
0 0 9
0 2 7
0 4 1
0 6 4
0 8 2
0 10 2
0 12 5
0 14 10
0 16 7
0 18 4
0 20 4
0 22 9
0 24 8
0 26 4
0 28 8
0 30 5
0 32 4
0 34 9
0 36 3
0 38 7
0 40 4
0 42 10
0 44 4
0 46 6
0 48 3
0 50 7
0 52 9
0 54 7
0 56 8
0 58 8
0 60 4
0 62 10
0 64 2
0 66 4
0 68 4
0 70 1
0 72 1
0 74 6
0 76 1
0 78 4
0 80 3
0 82 7
0...

output:

11450541
4243564198

result:

ok The answer is correct.

Test #50:

score: 10
Accepted
time: 104ms
memory: 28240kb

input:

200000
0 0 6
0 2 7
0 4 10
0 6 6
0 8 2
0 10 4
0 12 5
0 14 10
0 16 4
0 18 7
0 20 7
0 22 4
0 24 10
0 26 9
0 28 6
0 30 4
0 32 7
0 34 1
0 36 6
0 38 1
0 40 5
0 42 7
0 44 10
0 46 4
0 48 4
0 50 7
0 52 2
0 54 1
0 56 10
0 58 5
0 60 4
0 62 3
0 64 6
0 66 6
0 68 8
0 70 2
0 72 3
0 74 3
0 76 4
0 78 6
0 80 4
0 82 5...

output:

11450285
912738561

result:

ok The answer is correct.

Subtask #7:

score: 15
Accepted

Test #51:

score: 15
Accepted
time: 1002ms
memory: 46104kb

input:

200000
-1099 1879 7
1402 -488 8
-9770 8838 3
-177 -1714 9
2929 1099 9
4906 385 1
1606 5775 10
-2824 3929 10
997 2113 8
2897 -1592 4
-1679 8134 10
1988 405 4
-124 -112 5
-7851 12185 10
-2048 -1963 10
140 -2168 4
16857 -9907 4
-2719 10 8
1383 -648 9
2161 -464 9
1917 -1321 3
607 -2034 10
-22 1839 6
-30...

output:

19734513
437286793

result:

ok The answer is correct.

Test #52:

score: 15
Accepted
time: 938ms
memory: 47568kb

input:

200000
2025 -365 3
192 -989 2
-166 986 7
431 1549 5
-602 -1645 6
207 -1023 9
534 984 3
676 9091 4
745 918 1
-425 -924 6
3527 3958 8
701 -837 2
-1064 120 8
780 -633 9
924 -404 6
176 -1493 1
-408 -1293 7
392 1194 8
-1 -1026 9
985 203 2
565 -1105 5
1360 1222 4
-963 952 1
-797 -683 4
-1080 80 4
-4334 -2...

output:

20418521
3822459693

result:

ok The answer is correct.

Test #53:

score: 15
Accepted
time: 1002ms
memory: 46264kb

input:

200000
13552 17504 10
55022 32719 9
6200 166 9
12945 -1599 6
-84 -9370 9
2272 2045 6
-5507 -1106 3
9922 1421 4
-2123 2097 8
-15985 -4727 5
68779 -145950 8
-1932 -629 1
-7917 -25879 3
1848 -1192 1
-15989 1931 9
-1523 -272 9
-941 -355 10
5327 2204 8
1169 2819 5
2275 -3422 6
1573 6913 7
-2201 2090 2
-1...

output:

19831234
1580906305

result:

ok The answer is correct.

Test #54:

score: 15
Accepted
time: 963ms
memory: 43448kb

input:

200000
-205372 172615 10
-690170 811630 3
-216463 18700 9
73848 -298405 1
-71530 147610 3
176918 781471 9
-100671 171512 1
-11926 265100 3
-614730 66630 2
61240 202757 2
-337080 -79740 6
-419510 -150360 10
-129851 -37571 2
187124 138280 1
126131 21563 3
669380 409740 10
255945 75077 9
293388 375650 ...

output:

18911491
1845091104

result:

ok The answer is correct.

Test #55:

score: 15
Accepted
time: 588ms
memory: 37088kb

input:

200000
194822 -179435 9
386353 -539172 9
-100033 707090 2
494305 -104675 1
-523519 -167035 3
500211 46289 5
-196739 175627 2
919254 40944 6
-42219 286015 5
-669209 43270 3
127642 -791700 5
161655 -790679 8
-8599 -385866 2
-624868 60224 7
521623 -115619 1
474285 30937 2
-693024 13527 3
-267228 602102...

output:

16547899
2560856979

result:

ok The answer is correct.

Test #56:

score: 15
Accepted
time: 972ms
memory: 45384kb

input:

200000
3692 11527 3
-32458 -10378 1
-17330 7507 9
-107818 143665 2
3291 9114 9
-9838 -11390 6
-19483 17278 3
12060 -7189 8
-7646 17117 6
-15485 98577 1
2836 9589 10
-3321 3174 4
6306 13767 3
1262 -11963 5
-5522 7968 8
-5298 3701 7
2898 -2701 7
5765 -22534 8
1484 7721 4
-7098 1566 7
6285 -12209 7
247...

output:

18911890
3638350941

result:

ok The answer is correct.

Test #57:

score: 15
Accepted
time: 923ms
memory: 43224kb

input:

200000
-3488 -1565 7
-1553 -1626 2
822 200 9
-763 654 4
-41 -291 6
52 -605 5
-243 790 10
352 217 5
-373 -666 4
-364 130 5
-2978 -530 6
316 194 8
-401 -329 7
1159 495 4
-2148 -230 10
-1014 -373 10
259 -35 8
-169 739 8
-136 -850 2
288 256 3
58 -626 6
209 -376 2
4155 5267 9
2036 -96 7
351 -595 2
-2869 ...

output:

19308282
1647858833

result:

ok The answer is correct.

Test #58:

score: 15
Accepted
time: 674ms
memory: 46680kb

input:

200000
0 -4 7
0 1 6
0 -5 1
-2 0 6
2 5 4
5 -4 2
-3 2 5
-5 -5 4
363613 -181805 9
1 -2 5
0 8 6
0 -1 2
135010 -270022 4
139063 278128 5
8 7 2
2 0 3
-2 1 4
-4 0 1
1 0 4
57860 115714 7
-3 0 9
-166245 332500 6
7 5 10
159017 318038 7
0 0 5
-2 2 9
-60896 121803 10
-341683 -170838 1
3 -3 7
-4 -4 3
0 4 2
0 -3 ...

output:

13024274
1820041729

result:

ok The answer is correct.

Test #59:

score: 15
Accepted
time: 659ms
memory: 43404kb

input:

200000
2408 -4820 7
148902 -297798 10
-303339 455009 7
337003 337003 5
-290977 290968 8
1 2 4
9 9 3
-132931 -398803 3
2 0 4
-690986 -460661 8
-20606 30913 4
-1 3 2
-393156 393160 8
981089 -327030 2
-735752 -245249 9
557917 278963 8
7 3 10
-102296 204583 5
-993268 496632 6
-148390 445166 6
7 0 7
-449...

output:

15467695
2305420325

result:

ok The answer is correct.

Test #60:

score: 15
Accepted
time: 331ms
memory: 36512kb

input:

200000
-999859 -999861 1
-999708 -999716 2
-999892 -999898 4
-999838 -999836 2
-999854 -999852 10
-999640 -999649 5
-999980 -999984 1
-999723 -999726 7
-999696 -999709 4
-999718 -999711 1
-999758 -999750 8
-999814 -999811 10
-999855 -999857 6
-999739 -999740 5
-999921 -999935 7
-999926 -999941 8
-99...

output:

12082172
3517260828

result:

ok The answer is correct.

Test #61:

score: 15
Accepted
time: 319ms
memory: 37004kb

input:

200000
-999884 -999884 10
-999799 -999806 9
-999833 -999823 9
-999852 -999839 3
-999676 -999678 7
-999906 -999902 1
-999986 -999998 3
-999617 -999614 4
-999769 -999769 4
-999924 -999923 1
-999951 -999953 5
-999650 -999647 2
-999904 -999900 5
-999826 -999835 5
-999646 -999641 10
-999666 -999655 9
-99...

output:

12079960
545868298

result:

ok The answer is correct.

Subtask #8:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #62:

score: 15
Accepted
time: 1017ms
memory: 44400kb

input:

200000
-23039 -11004 8
2001 4576 3
-1858 -364 4
571 3592 10
391 960 7
-3406 -2685 2
23302 -64310 1
-4119 -13769 8
11130 593 8
-2027 1966 2
-9109 -1311 8
-7831 70828 8
-3224 6182 9
-2923 58 6
-4745 4923 3
648 -1977 6
601 -1806 7
4539 8124 4
5080 46 5
35259 30537 6
2192 1226 4
541 -1803 3
1438 2315 6
...

output:

19730066
1229424386

result:

ok The answer is correct.

Test #63:

score: 15
Accepted
time: 948ms
memory: 46748kb

input:

200000
-212 1189 10
-27980 -11367 9
1553 405 2
2081 -228 9
-769 5223 8
82 -1047 6
622 3992 6
1645 -3506 8
518 1169 8
1044 504 2
1068 464 3
-23 5735 10
-1054 -1436 10
1409 -226 7
-4987 3110 4
-429 -1013 9
-2384 -135 7
126 1046 8
1009 -105 4
-519 -4748 5
-552 -931 10
-2707 6206 3
2687 2929 6
722 821 2...

output:

20490410
1826363665

result:

ok The answer is correct.

Test #64:

score: 15
Accepted
time: 1000ms
memory: 46408kb

input:

200000
3491 3528 2
-6461 1966 1
-4884 5578 2
-6848 -2321 8
-2528 3846 3
1621 -984 1
11591 -7959 2
1374 194 3
2365 8303 7
1847 -975 8
682 -1052 9
-2113 2413 7
7099 1186 4
10387 34223 2
-6735 -3416 9
1971 -3550 6
8623 5274 9
3302 737 9
973 -5766 8
2493 4025 8
-2788 2910 1
25 4062 3
-5757 -6416 3
-999 ...

output:

19864817
2720736420

result:

ok The answer is correct.

Test #65:

score: 15
Accepted
time: 972ms
memory: 48240kb

input:

200000
-311102 447071 4
-307044 91412 1
-153794 -220767 2
64057 123159 9
-258227 -284908 8
-4628 78605 4
-62946 -57616 6
-340694 375467 10
-716125 973440 3
-251403 364275 2
-186235 3376 3
29309 -206317 2
16100 -494035 10
83196 -109093 2
94175 -329412 5
27052 166627 3
182097 -8069 4
-288202 686000 4
...

output:

18904039
2657834667

result:

ok The answer is correct.

Test #66:

score: 15
Accepted
time: 593ms
memory: 36840kb

input:

200000
344862 -601103 2
798163 165564 1
263298 -702207 9
-55551 376789 7
-639055 104695 5
-139395 -9034 3
23420 -131875 5
107674 659726 10
19775 -316444 3
340394 -263920 1
441882 -357512 8
-114748 -759168 8
161990 606697 6
-709434 -74027 4
-594498 391643 7
-23558 -129892 10
-765277 97109 10
-16136 -...

output:

16547966
1108005298

result:

ok The answer is correct.

Test #67:

score: 15
Accepted
time: 975ms
memory: 44936kb

input:

200000
-8405 5429 6
-4668 8501 5
79147 -145574 2
-7087 -8168 5
746 4403 5
-9899 -1411 10
-9614 6849 4
-3562 -7695 4
-1370 11729 3
1979 -1822 7
-12980 -11860 3
7510 3264 5
-4219 6702 10
-4929 3709 10
-5658 7178 8
1808 -10555 5
-714 29464 3
-13860 -588 1
112193 123456 1
-861 -5409 8
-9574 15432 5
1294...

output:

18888807
2422735470

result:

ok The answer is correct.

Test #68:

score: 15
Accepted
time: 928ms
memory: 44876kb

input:

200000
705 242 4
247 -464 2
-1618 -1205 1
-21 699 10
466 329 9
-743 -197 5
-273 -144 10
2061 1467 9
-199 183 5
-463 -46 1
-1372 316 10
2668 -120 5
-569 -502 8
-121 -1111 9
-311 -1271 3
4355 -2218 6
3711 1910 8
-689 226 6
42 -161 9
-3601 5527 9
369 136 3
239 97 9
-235 197 2
128 -54 3
-1591 435 7
142 ...

output:

19283548
681162568

result:

ok The answer is correct.

Test #69:

score: 15
Accepted
time: 698ms
memory: 46572kb

input:

200000
-78874 -157754 7
23746 -47497 2
0 -5 9
3 -1 8
-5 0 9
-460487 230246 5
965475 -482735 8
2741 5475 1
-1 -3 8
-1 3 8
-2 -2 6
246051 492104 3
1 2 5
6 6 1
1 -3 7
-195852 -97928 7
0 0 1
932769 466382 3
-1 -4 5
0 -2 10
1 -4 10
-4 0 5
0 -4 7
7 0 2
1 0 7
0 -3 10
2 2 10
3 0 9
5 -3 4
132108 -264223 10
-...

output:

13002482
3670441647

result:

ok The answer is correct.

Test #70:

score: 15
Accepted
time: 656ms
memory: 43932kb

input:

200000
2 -1 8
4 3 4
382881 -382879 1
-102771 102773 10
-4 -1 6
-493613 -493618 3
-228148 342227 2
249973 -499954 6
60653 -30330 4
0 0 4
-507581 -126893 7
-1 -1 5
-8610 -25832 10
46 -18 7
818897 -272963 5
473706 -473708 2
-549195 411897 8
-166093 -83050 10
2 1 2
716082 -358040 2
6 -4 10
-123296 30822...

output:

15503321
1863398598

result:

ok The answer is correct.

Test #71:

score: 15
Accepted
time: 333ms
memory: 34320kb

input:

200000
-999778 -999771 8
-999677 -999685 6
-999680 -999679 8
-999831 -999830 3
-999956 -999942 3
-999813 -999825 8
-999870 -999865 5
-999745 -999755 3
-999730 -999741 5
-999936 -999941 7
-999714 -999714 9
-999731 -999738 9
-999682 -999695 1
-999736 -999732 7
-999673 -999682 10
-999720 -999715 2
-999...

output:

12061100
3056059957

result:

ok The answer is correct.

Test #72:

score: 15
Accepted
time: 335ms
memory: 39640kb

input:

200000
-999704 -999704 7
-999633 -999623 5
-999953 -999958 6
-999934 -999942 5
-999988 -999990 4
-999929 -999925 8
-999965 -999966 6
-999889 -999901 8
-999661 -999664 7
-999876 -999877 6
-999629 -999629 8
-999630 -999635 1
-999828 -999818 1
-999805 -999809 8
-999629 -999623 10
-999686 -999684 4
-999...

output:

12090781
1209755738

result:

ok The answer is correct.