#include<bits/stdc++.h> #define F(i,l,r) for(int i=l;i<r;++i) #define Fe(i,l,r) for(int i=l;i<=r;++i) using std::max; namespace IO{ const int BUF_SZ=1<<16; char ib[BUF_SZ+1],*ip=ib+BUF_SZ; void ipre(int n){ int c=ib+BUF_SZ-ip; if(c<n){ memcpy(ib,ip,c); ip=ib; fread(ib+c,1,BUF_SZ-c,stdin)[ib+c]=0; } } template<class T> T read(T L,T R){ ipre(100); T x=0,f=1; while(*ip<'0'||*ip>'9')if(*ip++=='-')f=-f; while(*ip>='0'&&*ip<='9')x=x*10+*ip++-'0'; x*=f; if(!(L<=x&&x<=R)){ std::cerr<<x<<" not in ["<<L<<","<<R<<"]\n"; exit(1); } return x; } char ob[2<<24+1],*op=ob; void opre(int n){ int c=ob+BUF_SZ-op; if(c<n){ fwrite(ob,1,BUF_SZ-c,stdout); op=ob; } } template<class T> void write(T x){ opre(100); char ss[100],*sp=ss; if(x<0)x=-x,*op++='-'; do *sp++=x%10+'0';while(x/=10); while(sp!=ss)*op++=*--sp; } template<class T> void write(T x,char c){ write(x); *op++=c; } struct __{ __(){ } ~__(){ fwrite(ob,1,op-ob,stdout); } }_; }; int read(int L,int R){return IO::read(L,R);} constexpr int maxm=2e5,M=maxm+10,maxv=1e9; typedef long long i64; const int MEM=1<<26; char pool[MEM],*pool_p=pool; template<class T> void alloc(T *&p,int sz){ p=reinterpret_cast<T*>(pool_p); pool_p+=sz*sizeof(T); assert(pool_p<pool+MEM); F(i,0,sz)new(p+i)T(); } template<class T> struct Undo{ T &x; T x0; Undo(T &x):x(x),x0(x){} ~Undo(){x=x0;} }; #define alloc_scope Undo<char*> _(pool_p) template<class T> struct Inf{}; template<> struct Inf<i64>{ static const i64 value=1LL<<40; }; template<class T> struct Max{ T x; Max(T x=-Inf<T>::value):x(x){} Max<T> operator+(const Max<T> &w)const{return max(x,w.x);} void operator+=(const Max<T> &w){x=max(x,w.x);} }; template<class T> struct AddOp{ T x; AddOp(T x=T()):x(x){} void operator*=(const AddOp<T> &w){x+=w.x;} friend void operator*=(Max<T> &x,const AddOp<T> &y){x.x+=y.x;} }; template<class D,class M> struct MSegTree{ struct Node{ D d; M m; void app(const M &t){ d*=t; m*=t; } void up(const Node &a,const Node &b){ d=a.d+b.d; d*=m; } }*tr; int mx; void alloc(int n){ for(mx=1;mx<n+2;mx<<=1); ::alloc(tr,mx*2); } Node &at(int x){ return tr[mx+x]; } D &operator[](int x){ return tr[mx+x].d; } void range_update(int l,int r){ l+=mx,r+=mx; for(l>>=1,r>>=1;l<r;l>>=1,r>>=1){ Fe(x,l,r)up(x); } for(;l;l>>=1)up(l); } void up(int x){ tr[x].up(tr[x*2],tr[x*2+1]); } void update(const M &t){ tr[1].app(t); } void update_prefix(int x,const M &t){ for(x+=mx+1;x>1;x>>=1,up(x)){ if(x&1)tr[x-1].app(t); } } D query(){ return tr[1].d; } void dn(int x){ tr[x*2].app(tr[x].m); tr[x*2+1].app(tr[x].m); tr[x].m=M(); } void dna(int x){ x+=mx; for(int c=__builtin_ctz(mx);c>0;--c)dn(x>>c); } void dna(int l,int r){ l+=mx,r+=mx; for(int c=__builtin_ctz(mx);c>0;--c){ int L=l>>c,R=r>>c; Fe(i,L,R)dn(i); } } }; int m; struct Op{ int x,y,id; int a[2][2]; void R(int i){ x=read(2,m); y=read(2,m); id=i; F(i,0,2)F(j,0,2)a[i][j]=read(1,maxv); } }qs[M],qs2[M]; template<class T> struct Array{ T *v; int sz; Array(){} Array(int n){alloc(n);} void alloc(int n){ sz=n; ::alloc(v,n); } T &operator[](int x){ return v[x]; } }; template<class T> struct Grid{ T *v; int xsz,ysz; Grid(){} Grid(int xn,int yn){ alloc(xn,yn); } void alloc(int xn,int yn){ xsz=xn;ysz=yn; ::alloc(v,xn*yn); } T &operator()(int x,int y){ return v[x*ysz+y]; } }; struct Des{ int sz,x[M],id[M]; void clr(){ sz=0; } void ins(int a){ x[sz++]=a; } void build(){ ins(1),ins(m+1); std::sort(x,x+sz); sz=std::unique(x,x+sz)-x; F(i,1,sz)F(j,x[i-1],x[i])id[j]=i; } }xs,ys; struct NoD{ char _[0]; template<class T> void operator*=(const T &x){} friend NoD operator+(NoD a,NoD b){return NoD();} }; template<class T> struct HAddOp{ T h,a,a1; bool commit; HAddOp(T x=0):a1(x),commit(0){} void operator*=(const HAddOp<T> &w){ if(w.commit){ if(commit){ h=max(h,a+a1+w.h); a+=a1+w.a; a1=w.a1; }else{ h=a1+w.h; a=a1+w.a; a1=w.a1; commit=1; } }else{ a1+=w.a1; } } }; MSegTree<Max<i64>,AddOp<i64>> tr[M]; MSegTree<NoD,HAddOp<i64>> tr0; struct DC{ Array<int> x,y; Grid<MSegTree<Max<i64>,AddOp<i64>>::Node> g; void set_sz(int sz){ x.alloc(sz); y.alloc(sz); } void run(int m1){ int sz=x.sz; if(sz==1){ F(i,0,2)F(j,0,2){ IO::write(g(i,j).d.x,'\n'); g(i,j).app(qs[m1].a[i][j]); } return; } int o=0; F(I,0,2){ alloc_scope; int sz1=(I?sz-sz/2:sz/2); DC dc; dc.set_sz(sz1); Array<int> xe(g.xsz),ye(g.ysz); F(i,0,sz1){ xe[x[o+i]]=1; ye[y[o+i]]=1; } xe[0]=ye[0]=0; F(i,1,xe.sz)xe[i]+=xe[i-1]; F(i,1,ye.sz)ye[i]+=ye[i-1]; F(i,0,sz1){ dc.x[i]=xe[x[o+i]]; dc.y[i]=ye[y[o+i]]; } dc.g.alloc(xe[xe.sz-1]+1,ye[ye.sz-1]+1); F(i,0,g.xsz)F(j,0,g.ysz){ dc.g(xe[i],ye[j]).d+=g(i,j).d; } dc.run(m1+o); if(!I) F(i,0,g.xsz)F(j,0,g.ysz){ auto v=dc.g(xe[i],ye[j]).m; g(i,j).d*=v; g(i,j).m=v; } if(I) F(i,0,g.xsz)F(j,0,g.ysz){ g(i,j).m*=dc.g(xe[i],ye[j]).m; } o+=sz1; } } }; i64 v0[M],v1[M]; void cal(int m1,int m2){ alloc_scope; xs.clr(); ys.clr(); F(i,m1,m2){ Op &q=qs[i]; xs.ins(q.x); ys.ins(q.y); } xs.build(); ys.build(); Grid<i64> g(xs.sz,ys.sz); F(i,1,ys.sz){ int L=ys.x[i-1],R=ys.x[i]; tr[i].alloc(R-L); F(j,L,R)tr[i][j-L+1]=v0[j]; tr[i].range_update(1,R-L); g(0,i)=tr[i].query().x; } tr0.alloc(ys.sz); F(i,1,ys.sz)tr0.at(i).m=0; int p=0; F(i,1,xs.sz){ int L=xs.x[i-1],R=xs.x[i]; F(x,L,R){ for(;p<m&&qs2[p].x==x;++p){ Op &q=qs2[p]; if(q.id>=m1)continue; int a1=q.a[1][0]-q.a[0][0]; int a2=q.a[1][1]-q.a[0][1]; a1-=a2; int w=ys.id[q.y],u=q.y+1-ys.x[w-1]; i64 a=tr[w].query().x; tr[w].update_prefix(u-1,a1); a=tr[w].query().x-a; tr0.dna(w); auto &w0=tr0.at(w); w0.app(a); tr0.update_prefix(w-1,a1); tr0.update(a2); } HAddOp<i64> m; m.h=m.a=m.a1=0; m.commit=1; tr0.update(m); } tr0.dna(1,ys.sz); F(w,1,ys.sz){ auto &w0=tr0.at(w).m; g(i,w)=g(0,w)+w0.h; g(0,w)+=w0.a; w0=0; } } int m0=m2-m1; DC dc; dc.set_sz(m0); dc.g.alloc(xs.sz-1,ys.sz-1); F(i,1,xs.sz)F(j,1,ys.sz)dc.g(i-1,j-1).d=g(i,j); F(i,0,m0){ Op &q=qs[m1+i]; dc.x[i]=xs.id[q.x]-1; dc.y[i]=ys.id[q.y]-1; } dc.run(m1); Fe(i,1,m)v1[i]=0; F(i,m1,m2){ Op &q=qs[i]; v1[1]+=q.a[0][0]; v1[q.y]+=q.a[0][1]-q.a[0][0]; } v0[1]+=v1[1]; Fe(i,2,m)v1[i]+=v1[i-1],v0[i]+=v1[i]; } int main(){ m=read(1,maxm); F(i,0,m)qs[i].R(i); F(i,0,m)qs2[i]=qs[i]; std::sort(qs2,qs2+m,[](const Op &a,const Op &b){return a.x<b.x;}); int B=sqrt(m*6); for(int l=0,r;l<m;l=r){ r=std::min(l+B,m); cal(l,r); } return 0; }