#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; int a[MXN],b[MXN],c[MXN],d[MXN]; set<int>SC,SD; int s[MXN]; int* tmp; inline int rkb(int 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]; 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){ 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){ 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){ 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); } stack<pair<int,node>>RV; inline void chkmodc(int x,int l,int r,int L,int R,int c){ if(L>R)return ; if(c<=T[x].mnc)return ; if(L<=l&&r<=R&&c>=T[x].mxc){ uc(x,c); return ; } RV.push({lc(x),T[lc(x)]}); RV.push({rc(x),T[rc(x)]}); 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 ; } RV.push({lc(x),T[lc(x)]}); RV.push({rc(x),T[rc(x)]}); 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);} inline int gt(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return T[x].mnw; RV.push({lc(x),T[lc(x)]}); RV.push({rc(x),T[rc(x)]}); pd(x); int mid=l+r>>1; int res=4e9+1; if(L<=mid)res=max(res,gt(lc(x),l,mid,L,R)); if(R>mid)res=max(res,gt(rc(x),mid+1,r,L,R)); return res; } inline void clr(){ while(!RV.empty())RV.pop(); RV.push({1,T[1]}); } inline void rvk(){ while(!RV.empty()){ T[p1(RV.top())]=p2(RV.top()); RV.pop(); } } inline void chkmx(int x){ chkmxc(rkb(b[x])-1,c[x]); chkmxd(rkb(b[x])-1,d[x]); clr(); } int sc[MXN],sd[MXN]; int p[MXN]; inline bool cmp(int x,int y){ return a[x]<a[y]; } signed main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); ios::sync_with_stdio(0); int t; cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i]>>d[i], s[i]=b[i], p[i]=i; sort(s+1,s+n+1); tmp=unique(s+1,s+n+1); for(auto i=tmp;i!=s+n+1;i++) *i=4e9; sort(p+1,p+n+1,cmp); int res=1e18; bd(1,1,n); int mn=1e9; sc[n+1]=sd[n+1]=-1; 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]]); for(int i=1;i<=n;i++){ mn=min(mn,b[p[i]]); chkmx(p[i]); chkmxc(n,sc[i+1]); chkmxd(n,sd[i+1]); res=min(res,a[p[i]]+gt(1,1,n,rkb(mn),n)); rvk(); } cout<<res<<endl; } return 0; } /* */