#pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize(2) #include #include #include #define inf -2147483647 #define Re register int #define F(x,a,b) for(Re x=a;x<=b;++x) using namespace std; const int N=1e5+3,T=330; int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T],a[N],b[N],add[T]; inline void in(Re &x){ x=fu=0;char c=getchar(); while(c<'0'||c>'9')fu|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=fu?-x:x; } inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);} inline void change(Re l,Re r,Re x){ Re p=pt[l],q=pt[r]; if(p==q)sak(l,r,p,x); else{ F(i,p+1,q-1)add[i]+=x; sak(l,R[p],p,x),sak(L[q],r,q,x); } } inline int ask(Re l,Re r,Re x){ Re p=pt[l],q=pt[r],ans=inf,w; if(p==q){F(i,l,r)if(a[i]+add[p]=L[i]?max(ans,b[w]+add[i]):ans; F(i,l,R[p])if(a[i]+add[p]