struct SegTree{
    struct Node{
        int ls,rs;
        Info sum;
        Tag tag;
    }t[maxn<<2];
    int idx=1;
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define sum(p) t[p].sum
#define tag(p) t[p].tag
    int NewNode(){
        t[++idx]={};
        return idx;
    }
    void AddTag(int p,Tag k){
        tag(p)=tag(p)+k;
        sum(p)=sum(p)+k;
    }
    void PushDown(int p){
        if(tag(p)==Tag()) return;
        if(!ls(p)) ls(p)=NewNode();
        if(!rs(p)) rs(p)=NewNode();
        AddTag(ls(p),tag(p));
        AddTag(rs(p),tag(p));
        tag(p)={};
    }
    void PushUp(int p){
        sum(p)=sum(ls(p))+sum(rs(p));
    }
    void Add(int p,int l,int r,int L,int R,Tag k){
        if(l>R||r<L) return;
        if(L<=l&&R>=r) return AddTag(p,k);
        PushDown(p);
        int mid=l+((r-l)>>1);
        if(L<=mid){
            if(!ls(p)) ls(p)=NewNode();
            Add(ls(p),l,mid,L,R,k);
        }
        if(R>mid){
            if(!rs(p)) rs(p)=NewNode();
            Add(rs(p),mid+1,r,L,R,k);
        }
        PushUp(p);
    }
    void Change(int p,int l,int r,int x,Info k){
        if(l==r) return sum(p)=k,void();
        PushDown(p);
        int mid=l+((r-l)>>1);
        if(x<=mid){
            if(!ls(p)) ls(p)=NewNode();
            Change(ls(p),l,mid,x,k);
        }else{
            if(!rs(p)) rs(p)=NewNode();
            Change(rs(p),mid+1,r,x,k);
        }
        PushUp(p);
    }
    Info Query(int p,int l,int r,int L,int R){
        if(!p||l>R||r<L) return {};
        if(L<=l&&R>=r) return sum(p);
        PushDown(p);
        int mid=l+((r-l)>>1);
        return Query(ls(p),l,mid,L,R)+Query(rs(p),mid+1,r,L,R);
    }
    void Add(int l,int r,Tag k){
        Add(1,1,n,l,r,k);
    }
    Info Query(int l,int r){
        return Query(1,1,n,l,r);
    }
    void Change(int x,Info k){
        Change(1,1,n,x,k);
    }
    void Build(){
        idx=1;
        t[0]=t[1]={};
    }
};