typedef long long ll;
#define ls (rt<<1)
#define rs (ls|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
const ll maxn=1e5+55;
ll mod=123456789;
ll mul[maxn<<2],add[maxn<<2],sum[maxn<<2],a[maxn];

void push_down(ll rt,ll l,ll r){
    // if(l!=r) push_down(ls,l,ml),push_down(rs,mr,r);
    if(mul[rt]!=1){
        mul[ls]=mul[ls]*mul[rt]%mod;
        add[ls]=add[ls]*mul[rt]%mod;
        sum[ls]=sum[ls]*mul[rt]%mod;

        mul[rs]=mul[rs]*mul[rt]%mod;
        add[rs]=add[rs]*mul[rt]%mod;
        sum[rs]=sum[rs]*mul[rt]%mod;

        mul[rt]=1;
    }
    if(add[rt]!=0){
        add[ls]=(add[ls]+add[rt])%mod;
        sum[ls]=(sum[ls]+add[rt]*(ml-l+1))%mod;

        add[rs]=(add[rs]+add[rt])%mod;
        sum[rs]=(sum[rs]+add[rt]*(r-mr+1))%mod;

        add[rt]=0;
    }
}

void push_up(ll rt,ll l,ll r){
    sum[rt]=(sum[ls]+sum[rs])%mod;
}

void build(ll rt,ll l,ll r){
    mul[rt]=1;
    add[rt]=0;
    if(l==r){
        sum[rt]=a[l];
    }
    else{
        build(ls,l,ml);
        build(rs,mr,r);
        push_up(rt,l,r);
    }
}

void update_add(ll rt,ll l,ll r,ll ql,ll qr,ll d){
    if(l!=r)push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        sum[rt]=(sum[rt]+(r-l+1)*d)%mod;
        add[rt]=d;
    }
    else{
        if(ml>=ql) update_add(ls,l,ml,ql,qr,d);
        if(mr<=qr) update_add(rs,mr,r,ql,qr,d);
        push_up(rt,l,r);
    }
}

void update_mul(ll rt,ll l,ll r,ll ql,ll qr,ll d){
    if(l!=r)push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        sum[rt]=sum[rt]*d%mod;
        mul[rt]=d;
    }
    else{
        if(ml>=ql) update_mul(ls,l,ml,ql,qr,d);
        if(mr<=qr) update_mul(rs,mr,r,ql,qr,d);
        push_up(rt,l,r);
    }
}

ll query_sum(ll rt,ll l,ll r,ll ql,ll qr){
    if(l!=r)push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        ll ret=0;
        if(ml>=ql) ret+=query_sum(ls,l,ml,ql,qr);
        if(mr<=qr) ret+=query_sum(rs,mr,r,ql,qr);
        return ret%mod;
    }
}