#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; int n,b; 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],tag[1005][1005]; ll val2[15][1005][1005]; int xl[1005],xr[1005],yl[1005],yr[1005]; void sol(int l,int r,int u){ if(l==r){ up(i,1,2)up(j,1,2)printf("%lld\n",val2[u][i][j]); return; } int mid=l+r>>1; auto init=[&](int l,int r,vector<int>&X,vector<int>&Y){ X={0,n},Y={0,n}; up(i,l,r)X.eb(d[i].x-1),Y.eb(d[i].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()); }; vector<int>X,Y,X2,Y2; init(l,r,X,Y),init(l,mid,X2,Y2); int b1=X2.size()-1,b2=Y2.size()-1; up(i,1,b1)xl[i]=lower_bound(X.begin(),X.end(),X2[i-1])-X.begin()+1,xr[i]=lower_bound(X.begin(),X.end(),X2[i])-X.begin(); up(i,1,b2)yl[i]=lower_bound(Y.begin(),Y.end(),Y2[i-1])-Y.begin()+1,yr[i]=lower_bound(Y.begin(),Y.end(),Y2[i])-Y.begin(); up(i,1,b1)up(j,1,b2){ll mx=-inf;up(p,xl[i],xr[i])up(q,yl[j],yr[j])mx=max(mx,val2[u][p][q]);val2[u+1][i][j]=mx;} sol(l,mid,u+1);b1=X.size()-1,b2=Y.size()-1;up(i,1,b1+1)up(j,1,b2+1)tag[i][j]=0; up(i,l,mid){ int x=lower_bound(X.begin(),X.end(),d[i].x-1)-X.begin(); int y=lower_bound(Y.begin(),Y.end(),d[i].y-1)-Y.begin(); tag[b1][b2]+=d[i].d; tag[x][b2]+=d[i].b-d[i].d; tag[b1][y]+=d[i].c-d[i].d; tag[x][y]+=d[i].a+d[i].d-d[i].b-d[i].c; } down(i,b1,1)down(j,b2,1)tag[i][j]+=tag[i][j+1]; down(i,b1,1)down(j,b2,1)tag[i][j]+=tag[i+1][j]; up(i,1,b1)up(j,1,b2)val2[u][i][j]+=tag[i][j]; init(mid+1,r,X2,Y2);b1=X2.size()-1,b2=Y2.size()-1; up(i,1,b1)xl[i]=lower_bound(X.begin(),X.end(),X2[i-1])-X.begin()+1,xr[i]=lower_bound(X.begin(),X.end(),X2[i])-X.begin(); up(i,1,b2)yl[i]=lower_bound(Y.begin(),Y.end(),Y2[i-1])-Y.begin()+1,yr[i]=lower_bound(Y.begin(),Y.end(),Y2[i])-Y.begin(); up(i,1,b1)up(j,1,b2){ll mx=-inf;up(p,xl[i],xr[i])up(q,yl[j],yr[j])mx=max(mx,val2[u][p][q]);val2[u+1][i][j]=mx;}sol(mid+1,r,u+1); } void slv(){ n=read(),b=550; 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; for(int i=1;i<=n;i+=b){ int r=min(i+b-1,n); X={0,n},Y={0,n}; up(j,i,r)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()); 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,n,d[j].c-d[j].a),op[d[j].x].eb(d[j].y,n,d[j].d-d[j].b-(d[j].c-d[j].a)); } 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]); up(i,1,b1)up(j,1,b2)val2[0][i][j]=val[i][j];sol(i,r,0); } } int main(){ // freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout); slv(); return 0; }