#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,_inf=1e15; int n; ll sum[maxn]; struct tree{ struct node{ int l,r,ls,rs; ll mx,hmx,lz,hlz; void addo(){hmx=hlz=-inf;} void addv(ll x){lz+=x,mx+=x;} void addh(ll x){hmx=max(hmx,mx+x),hlz=max(hlz,lz+x);} }d[maxn<<2]; #define ls(p) d[p].ls #define rs(p) d[p].rs int tot; void pu(int p){d[p].mx=max(d[ls(p)].mx,d[rs(p)].mx),d[p].hmx=max(d[ls(p)].hmx,d[rs(p)].hmx);} void pd(int p){ if(d[p].hlz!=-inf)d[ls(p)].addh(d[p].hlz),d[rs(p)].addh(d[p].hlz),d[p].hlz=-inf; if(d[p].lz)d[ls(p)].addv(d[p].lz),d[rs(p)].addv(d[p].lz),d[p].lz=0; } void cl(int p,int l,int r){d[p].l=l,d[p].r=r,d[p].ls=d[p].rs=0;d[p].lz=0,d[p].hlz=-inf;} void bd(int l,int r,int &p){ cl(p=++tot,l,r); if(l==r){d[p].mx=d[p].hmx=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,ll x){ int s=d[p].l,t=d[p].r; if(l<=s&&t<=r)return d[p].addh(x),d[p].addv(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]=d[p].hmx,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]; const int b=1e3; ll val[b+5][b+5],tag[b+5][b+5]; ll val2[15][b+5][b+5]; int xl[b+5],xr[b+5],yl[b+5],yr[b+5]; 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(); 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; 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){ up(j,X[i-1]+1,X[i])if(j!=1){ for(auto [l,r,v]:op[j])if(v<0)t.mdf(l,r,1,v); for(auto [l,r,v]:op[j])if(v>=0)t.mdf(l,r,1,v); if(j==X[i-1]+1)t.mdf(1,n,1,_inf); } t.print(1,b2,1,val[i]); up(j,1,b2)val[i][j]-=_inf*(i-1); } // 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; }