#pragma once
// LazySegmentTreetemplate<typenameT,typenameE,typenameF,typenameG,typenameH>structLazySegmentTree{intn,height;Ff;Gg;Hh;Tti;Eei;vector<T>dat;vector<E>laz;LazySegmentTree(int_n,F_f,G_g,H_h,T_ti,E_ei):f(_f),g(_g),h(_h),ti(_ti),ei(_ei){init(_n);}LazySegmentTree(constvector<T>&v,F_f,G_g,H_h,T_ti,E_ei):f(_f),g(_g),h(_h),ti(_ti),ei(_ei){init((int)v.size());build(v);}voidinit(int_n){n=1;height=0;while(n<_n)n<<=1,height++;dat.assign(2*n,ti);laz.assign(2*n,ei);}voidbuild(constvector<T>&v){int_n=v.size();init(_n);for(inti=0;i<_n;i++)dat[n+i]=v[i];for(inti=n-1;i;i--)dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);}inlineTreflect(intk){returnlaz[k]==ei?dat[k]:g(dat[k],laz[k]);}inlinevoideval(intk){if(laz[k]==ei)return;laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);dat[k]=reflect(k);laz[k]=ei;}inlinevoidthrust(intk){for(inti=height;i;i--)eval(k>>i);}inlinevoidrecalc(intk){while(k>>=1)dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));}voidupdate(inta,intb,Ex){if(a>=b)return;thrust(a+=n);thrust(b+=n-1);for(intl=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1)laz[l]=h(laz[l],x),l++;if(r&1)--r,laz[r]=h(laz[r],x);}recalc(a);recalc(b);}voidset_val(inta,Tx){thrust(a+=n);dat[a]=x;laz[a]=ei;recalc(a);}Tget_val(inta){thrust(a+=n);returnreflect(a);}Tquery(inta,intb){if(a>=b)returnti;thrust(a+=n);thrust(b+=n-1);Tvl=ti,vr=ti;for(intl=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1)vl=f(vl,reflect(l++));if(r&1)vr=f(reflect(--r),vr);}returnf(vl,vr);}};