using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; static class Program{ const int mod=(int)1e9+7; const double eps=1e-11; static void Main(){ Sc sc=new Sc(); var n=sc.I; var a=sc.Ia; var h=new int[n][]; Fc2 fc=new Fc2(); for(int i = 0;i> li=new List>(); public Nd1(int x,int y,long d,Nd du):base(x){ li.Add(Tuple.Create(y,d)); l=r=du; } public override void Ad(int y,long d){li.Add(Tuple.Create(y,d));} } public Nd root,du; public int cnt=0; private bool bo=false; public Fc2(){ du=new Nd(int.MinValue);du.h=0; root=du; } public void Ud(int x,int y,long d){ if(!root.lf){ Fu(root,x,y,d); if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);} } else if(root!=du){ if(root.x!=x){root=Flf(root,x,y,d);} else{root.Ad(y,d);} } else{root=new Nd1(x,y,d,du);} cnt++; } private void Fu(Nd t,int x,int y,long d){ if(t.x>x){ if(!t.l.lf){ Fu(t.l,x,y,d); if(Abs(t.l.l.h-t.l.r.h)>1){t.l=Rotate(t.l);} } else if(t.l.x!=x){t.l=Flf(t.l,x,y,d);} else{t.l.Ad(y,d);} } else{ if(!t.r.lf){ Fu(t.r,x,y,d); if(Abs(t.r.l.h-t.r.r.h)>1){t.r=Rotate(t.r);} } else if(t.r.x!=x){t.r=Flf(t.r,x,y,d);} else{t.r.Ad(y,d);} } t.h=Max(t.l.h,t.r.h)+1; } private Nd Flf(Nd t,int x,int y,long d){ var e=new Nd1(x,y,d,du); return t.x>x?new Nd(t.x,e,t):new Nd(x,t,e); } private Nd Rotate(Nd t){ Nd nd=du; if(t.l.h>t.r.h){ if(t.l.l.h>t.l.r.h){ nd=t.l;t.l=t.l.r;nd.r=t; Ft(t); } else{ nd=t.l.r; t.l.r=nd.l;nd.l=t.l; Ft(t.l); t.l=nd.r;nd.r=t; Ft(t); } } else{ if(t.r.l.h>t.r.r.h){ nd=t.r.l; t.r.l=nd.r;nd.r=t.r; Ft(t.r); t.r=nd.l;nd.l=t; Ft(t); } else{ nd=t.r;t.r=t.r.l;nd.l=t; Ft(t); } } Ft(nd); return nd; } private void Ft(Nd t){ if(!t.lf){t.h=Max(t.l.h,t.r.h)+1;} } public long Get(int x1,int x2,int y1,int y2){ if(!bo){Dn();} int lb=-1,ub=root.dat1.Length,mid=0; while(ub-lb>1){ mid=(ub+lb)>>1; if(root.dat1[mid]>y2){ub=mid;} else{lb=mid;} } int p=ub; lb=-1;ub=root.dat1.Length; while(ub-lb>1){ mid=(ub+lb)>>1; if(root.dat1[mid]>=y1){ub=mid;} else{lb=mid;} } return Fdg(root,x1,x2,false,false,ub,p); } private long Fdg(Nd t,int a,int b,bool l,bool r,int la,int ra){ if(t.lf){ if(a<=t.x&&t.x<=b){return t.dat4[ra]-t.dat4[la];} else{return 0;} } if(l&&r){return t.dat4[ra]-t.dat4[la];} if(t.x>b){return Fdg(t.l,a,b,l,t.x<=b,t.dat2[la],t.dat2[ra]);} if(t.x=a,r,t.dat3[la],t.dat3[ra]);} return Fdg(t.l,a,b,l,t.x<=b,t.dat2[la],t.dat2[ra])+Fdg(t.r,a,b,t.x>=a,r,t.dat3[la],t.dat3[ra]); } private void Dn(){ Fu(root); bo=true; } private void Fu(Nd t){ if(t.lf){ var z=(Nd1)t; z.li.Sort((u,v)=>u.Item1-v.Item1); z.m=z.li.Count; z.dat1=new int[z.m]; z.dat4=new long[z.m+1]; for(int i = 0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i