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;
}
}