#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10; const ll inf=1e18; struct mat{ll a00,a01,a11;}; inline mat operator*(mat a,mat b){ mat c;c.a00=c.a01=c.a11=-inf; c.a00=max(c.a00,a.a00+b.a00); c.a01=max(c.a01,a.a00+b.a01); c.a01=max(c.a01,a.a01+b.a11); c.a11=max(c.a11,a.a11+b.a11); return c; } struct vec{ll a0,a1;}; inline vec operator*(vec a,mat b){ vec c;c.a0=c.a1=-inf; c.a0=max(c.a0,a.a0+b.a00); c.a1=max(c.a1,a.a0+b.a01); c.a1=max(c.a1,a.a1+b.a11); return c; } inline vec operator+(vec a,vec b){ a.a0=max(a.a0,b.a0),a.a1=max(a.a1,b.a1); return a; } inline void init(mat&x){x.a00=x.a11=0,x.a01=-inf;} ll sum[maxn]; struct tree{ vec T[maxn<<2]; mat lz[maxn<<2]; struct node{ int l,r,ls,rs; }d[maxn<<2]; #define ls(p) d[p].ls #define rs(p) d[p].rs int tot; void add(int p,mat&x){lz[p]=lz[p]*x,T[p]=T[p]*x;} void pu(int p){T[p]=T[ls(p)]+T[rs(p)];} void pd(int p){if(lz[p].a00==0&&lz[p].a01==-inf&&lz[p].a11==0)return;add(ls(p),lz[p]),add(rs(p),lz[p]);init(lz[p]);} void cl(int p,int l,int r){d[p].l=l,d[p].r=r,d[p].ls=d[p].rs=0;init(lz[p]);} void bd(int l,int r,int &p){ cl(p=++tot,l,r); if(l==r){T[p].a0=T[p].a1=sum[l];return;} int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } void BD(int l,int r,int &p,int *t){ if(l==r)return bd(t[l-1]+1,t[l],p),void(); cl(p=++tot,t[l-1]+1,t[r]); int mid=l+r>>1; BD(l,mid,ls(p),t),BD(mid+1,r,rs(p),t);pu(p); } void mdf(int l,int r,int p,mat&x){ int s=d[p].l,t=d[p].r; if(l<=s&&t<=r)return add(p,x),void();pd(p); int mid=d[ls(p)].r; if(l<=mid)mdf(l,r,ls(p),x);if(r>mid)mdf(l,r,rs(p),x);pu(p); } void print(int s,int t,int p,ll *ans){ if(s==t)return ans[s]=T[p].a1,void();pd(p); int mid=s+t>>1; print(s,mid,ls(p),ans),print(mid+1,t,rs(p),ans); } }t; struct node{ int x,y,a,b,c,d; }d[maxn]; vector<tuple<int,int,int> >op[maxn]; ll val[1005][1005]; struct tree2{ ll mx[maxn<<4],lz[maxn<<4]; void pu(int p){mx[p]=-inf;up(i,0,3)mx[p]=max(mx[p],mx[p<<2|i]);mx[p]+=lz[p];} void bd(int l1,int r1,int l2,int r2,int p){ lz[p]=0,mx[p]=-inf; if(l1>r1||l2>r2)return; if(l1==r1&&l2==r2)return mx[p]=val[l1][l2],void(); int mx=l1+r1>>1,my=l2+r2>>1; bd(l1,mx,l2,my,p<<2),bd(l1,mx,my+1,r2,p<<2|1); bd(mx+1,r1,l2,my,p<<2|2),bd(mx+1,r1,my+1,r2,p<<2|3);pu(p); } void mdf(int l1,int r1,int l2,int r2,int s1,int t1,int s2,int t2,int p,int x){ if(l1<=s1&&t1<=r1&&l2<=s2&&t2<=r2)return lz[p]+=x,mx[p]+=x,void(); int mx=s1+t1>>1,my=s2+t2>>1; if(l1<=mx&&l2<=my)mdf(l1,r1,l2,r2,s1,mx,s2,my,p<<2,x); if(l1<=mx&&r2>my)mdf(l1,r1,l2,r2,s1,mx,my+1,t2,p<<2|1,x); if(r1>mx&&l2<=my)mdf(l1,r1,l2,r2,mx+1,t1,s2,my,p<<2|2,x); if(r1>mx&&r2>my)mdf(l1,r1,l2,r2,mx+1,t1,my+1,t2,p<<2|3,x);pu(p); } ll qu(int l1,int r1,int l2,int r2,int s1,int t1,int s2,int t2,int p){ if(l1<=s1&&t1<=r1&&l2<=s2&&t2<=r2)return mx[p]; int mx=s1+t1>>1,my=s2+t2>>1;ll res=-inf; if(l1<=mx&&l2<=my)res=qu(l1,r1,l2,r2,s1,mx,s2,my,p<<2); if(l1<=mx&&r2>my)res=max(res,qu(l1,r1,l2,r2,s1,mx,my+1,t2,p<<2|1)); if(r1>mx&&l2<=my)res=max(res,qu(l1,r1,l2,r2,mx+1,t1,s2,my,p<<2|2)); if(r1>mx&&r2>my)res=max(res,qu(l1,r1,l2,r2,mx+1,t1,my+1,t2,p<<2|3)); return res+lz[p]; } }t2; void slv(){ int n=read(),b=450; up(i,1,n)d[i].x=read(),d[i].y=read(),d[i].a=read(),d[i].b=read(),d[i].c=read(),d[i].d=read(); vector<int>X,Y;mat mt; int b1=0,b2=0; up(i,1,n){ if(i%b==1){ X={0,n},Y={0,n}; up(j,i,min(i+b-1,n))X.eb(d[j].x-1),Y.eb(d[j].y-1); sort(X.begin(),X.end()),sort(Y.begin(),Y.end()); X.erase(unique(X.begin(),X.end()),X.end()); Y.erase(unique(Y.begin(),Y.end()),Y.end()); sort(Y.begin(),Y.end()); up(j,1,n)op[j].clear(),sum[j]=0; up(j,1,i-1){ sum[1]+=d[j].a,sum[d[j].y]+=d[j].b-d[j].a; op[d[j].x].eb(1,d[j].y-1,d[j].c-d[j].a),op[d[j].x].eb(d[j].y,n,d[j].d-d[j].b); } up(j,1,n)sum[j]+=sum[j-1]; b1=X.size()-1,b2=Y.size()-1; t.tot=0;int rt=0;t.BD(1,b2,rt,Y.data()); up(i,1,b1){ // cout<<"ins "<<X[i-1]+1<<" "<<X[i]<<endl; up(j,X[i-1]+1,X[i])if(j!=1){ for(auto [l,r,v]:op[j])init(mt),mt.a00=v,t.mdf(l,r,1,mt); init(mt);mt.a01=0;t.add(1,mt); } // cout<<"test"<<t.T[1].a[0]<<" "<<t.T[1].a[1]<<endl; t.print(1,b2,1,val[i]); init(mt);mt.a11=-inf;t.add(1,mt); } // up(i,1,b1)up(j,1,b2)printf("val[%d][%d]=%lld\n",i,j,val[i][j]); t2.bd(1,b1,1,b2,1); // puts("done"); } auto op=[&](int l1,int r1,int l2,int r2,int x){ l1=lower_bound(X.begin(),X.end(),l1-1)-X.begin()+1; r1=lower_bound(X.begin(),X.end(),r1)-X.begin(); l2=lower_bound(Y.begin(),Y.end(),l2-1)-Y.begin()+1; r2=lower_bound(Y.begin(),Y.end(),r2)-Y.begin(); printf("%lld\n",t2.qu(l1,r1,l2,r2,1,b1,1,b2,1)); t2.mdf(l1,r1,l2,r2,1,b1,1,b2,1,x); }; op(1,d[i].x-1,1,d[i].y-1,d[i].a); op(1,d[i].x-1,d[i].y,n,d[i].b); op(d[i].x,n,1,d[i].y-1,d[i].c); op(d[i].x,n,d[i].y,n,d[i].d); } } int main(){ // freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout); slv(); return 0; }