#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define p1(x) x.first #define p2(x) x.second int n; const int MXN=1e6+30; unsigned a[MXN],b[MXN],c[MXN],d[MXN],s[MXN]; unsigned* tmp; inline unsigned rkb(unsigned x){ return lower_bound(s+1,tmp,x)-s; } const int INF=4e9+1; struct node{ int mnw,mnx,mnc,mnd,mncx,mndx,tgc,tgd,mxc,mxd; }T[MXN<<2]; stack<pair<int,node>>RV; inline void upd(int x){ T[x].mnw=min(T[lc(x)].mnw,T[rc(x)].mnw); T[x].mnx=min(T[lc(x)].mnx,T[rc(x)].mnx); T[x].mnc=min(T[lc(x)].mnc,T[rc(x)].mnc); T[x].mnd=min(T[lc(x)].mnd,T[rc(x)].mnd); T[x].mncx=min(T[lc(x)].mncx,T[rc(x)].mncx); T[x].mndx=min(T[lc(x)].mndx,T[rc(x)].mndx); T[x].mxc=max(T[lc(x)].mxc,T[rc(x)].mxc); T[x].mxd=max(T[lc(x)].mxd,T[rc(x)].mxd); } inline void uc(int x,int c){ if(T[x].tgc==c)return ; T[x].tgc=c; T[x].mnw=T[x].mndx+c; T[x].mncx=T[x].mnx+c; T[x].mnc=c; T[x].mxc=c; } inline void ud(int x,int d){ if(T[x].tgd==d)return ; T[x].tgd=d; T[x].mnw=T[x].mncx+d; T[x].mndx=T[x].mnx+d; T[x].mnd=d; T[x].mxd=d; } inline void pd(int x){ if(T[x].tgc){ uc(lc(x),T[x].tgc); uc(rc(x),T[x].tgc); T[x].tgc=0; } if(T[x].tgd){ ud(lc(x),T[x].tgd); ud(rc(x),T[x].tgd); T[x].tgd=0; } } inline void bd(int x,int l,int r){ T[x]={0,0,0,0,0,0,0,0,0,0}; if(l==r){ T[x]={s[l],s[l],0,0,s[l],s[l],0,0,0,0}; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline void chkmodc(int x,int l,int r,int L,int R,int c){ if(L>R)return ; // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<c<<" "<<T[x].mnc<<endl; if(c<=T[x].mnc)return ; if(L<=l&&r<=R&&c>=T[x].mxc){ uc(x,c); // cout<<l<<"x"<<r<<"x"<<c<<"x"<<T[x].mnc<<"x"<<T[x].tgc<<endl; return ; } pd(x); int mid=l+r>>1; if(L<=mid)chkmodc(lc(x),l,mid,L,R,c); if(R>mid)chkmodc(rc(x),mid+1,r,L,R,c); upd(x); } inline void chkmxc(int r,int c){chkmodc(1,1,n,1,r,c);} inline void chkmodd(int x,int l,int r,int L,int R,int d){ if(L>R)return ; if(d<=T[x].mnd)return ; if(L<=l&&r<=R&&d>=T[x].mxd){ ud(x,d); return ; } pd(x); int mid=l+r>>1; if(L<=mid)chkmodd(lc(x),l,mid,L,R,d); if(R>mid)chkmodd(rc(x),mid+1,r,L,R,d); upd(x); } inline void chkmxd(int r,int d){chkmodd(1,1,n,1,r,d);} bool vis[MXN<<2]; inline void ps(int x,node T){ if(!vis[x]) vis[x]=1,RV.push({x,T}); } inline void ucrv(int x,int c){ if(T[x].tgc==c)return ; ps(x,T[x]); T[x].tgc=c; T[x].mnw=T[x].mndx+c; T[x].mncx=T[x].mnx+c; T[x].mnc=c; T[x].mxc=c; } inline void udrv(int x,int d){ if(T[x].tgd==d)return ; ps(x,T[x]); T[x].tgd=d; T[x].mnw=T[x].mncx+d; T[x].mndx=T[x].mnx+d; T[x].mnd=d; T[x].mxd=d; } inline void pdrv(int x){ if(T[x].tgc){ ucrv(lc(x),T[x].tgc); ucrv(rc(x),T[x].tgc); T[x].tgc=0; } if(T[x].tgd){ udrv(lc(x),T[x].tgd); udrv(rc(x),T[x].tgd); T[x].tgd=0; } } inline void chkmodcrv(int x,int l,int r,int L,int R,int c){ if(L>R)return ; // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<c<<" "<<T[x].mnc<<endl; if(c<=T[x].mnc)return ; if(L<=l&&r<=R&&c>=T[x].mxc){ ucrv(x,c); // cout<<l<<"?"<<r<<"x"<<c<<"x"<<T[x].mnc<<"x"<<T[x].tgc<<endl; return ; } pdrv(x); int mid=l+r>>1; if(L<=mid)chkmodcrv(lc(x),l,mid,L,R,c); if(R>mid)chkmodcrv(rc(x),mid+1,r,L,R,c); ps(x,T[x]); upd(x); } inline void chkmxcrv(int r,int c){chkmodcrv(1,1,n,1,r,c);} inline void chkmoddrv(int x,int l,int r,int L,int R,int d){ if(L>R)return ; if(d<=T[x].mnd)return ; if(L<=l&&r<=R&&d>=T[x].mxd){ udrv(x,d); // cout<<l<<"x"<<r<<"x"<<d<<"x"<<T[x].mnw<<endl; return ; } pdrv(x); int mid=l+r>>1; if(L<=mid)chkmoddrv(lc(x),l,mid,L,R,d); if(R>mid)chkmoddrv(rc(x),mid+1,r,L,R,d); ps(x,T[x]); upd(x); } inline void chkmxdrv(int r,int d){chkmoddrv(1,1,n,1,r,d);} inline int gt(int x,int l,int r,int L,int R){ if(L>R)return 4e9+1; if(L<=l&&r<=R)return T[x].mnw; pdrv(x); int mid=l+r>>1; int res=4e9+1; if(L<=mid)res=min(res,gt(lc(x),l,mid,L,R)); if(R>mid)res=min(res,gt(rc(x),mid+1,r,L,R)); return res; } inline void clr(){ while(!RV.empty())RV.pop(); RV.push({1,T[1]}); vis[1]=1; } inline void rvk(){ while(!RV.empty()){ auto e=RV.top(); T[p1(e)]=p2(e); vis[p1(e)] =0; RV.pop(); } } inline void chkmx(int x){ int t=rkb(b[x]); // cout<<t<<" "<<c[x]<<" "<<d[x]<<endl; chkmxc(t-1,c[x]); chkmxd(t-1,d[x]); // clr(); } unsigned sc[MXN],sd[MXN],sa[MXN],sb[MXN]; int p[MXN]; inline bool cmp(int x,int y){ if(a[x]==a[y])return b[x]<b[y]; return a[x]<a[y]; } #define rd(x) scanf("%lld",&x) signed main() { // freopen("inter.in","r",stdin); // freopen("inter.out","w",stdout); ios::sync_with_stdio(0); int t; rd(t); while(t--){ rd(n); for(int i=1;i<=n;i++)rd(a[i]),rd(b[i]),rd(c[i]),rd(d[i]), s[i]=b[i], p[i]=i; if(n==1){ printf("%lld\n",a[1]+b[1]+c[1]+d[1]); continue; } sort(s+1,s+n+1); tmp=unique(s+1,s+n+1); for(auto i=tmp;i!=s+n+10;i++) *i=4e9; sort(p+1,p+n+1,cmp); int res=1e18; bd(1,1,n); unsigned mn=1e9; sc[n+1]=sd[n+1]=sa[n+1]=sb[n+1]=0; for(int i=n;i>=1;i--) sc[i]=max(sc[i+1],c[p[i]]), sd[i]=max(sd[i+1],d[p[i]]), sa[i]=max(sa[i+1],a[p[i]]), sb[i]=max(sb[i+1],b[p[i]]); unsigned mx=0; for(int i=1;i<=n;i++){ mn=min(mn,b[p[i]]); mx=max(mx,b[p[i]]); chkmx(p[i]); clr(); chkmxcrv(n,sc[i+1]); chkmxdrv(n,sd[i+1]); // printf("%lld %lld %lld \n",rkb(mn),a[p[i]],gt(1,1,n,rkb(mn),n)); if(T[1].mnw+a[p[i]]<res) res=min(res,a[p[i]]+gt(1,1,n,rkb(mn),i==n?rkb(mx)-1:n)); rvk(); } unsigned mxa=0,mxb=0; for(int i=1;i<=n;i++){ res=min(res,(int)max(mxa,sa[i+1])+max(mxb,sb[i+1])+c[p[i]]+d[p[i]]); mxa=max(mxa,a[p[i]]); mxb=max(mxb,b[p[i]]); } printf("%lld\n",res); } return 0; }