RT

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 4 * 1e5 + 10;
ll n,q,m = INT_MAX,f,x,y,k,tree[N],a[N],tagm[N],taga[N],le[N],ri[N]; //tree是线段树本体，ri和le是右端点和左端点，tagm是乘法标记，taga是加法标记
void buildtree(ll l,ll r,ll k)
{
    le[k] = l;
    ri[k] = r;
    tagm[k] = 1;
    taga[k] = 0;
    if(l == r){
        tree[k] = a[l];
        return;
    } 
    ll mid = l + r >> 1;
    buildtree(l,mid,k << 1);
    buildtree(mid + 1,r,k << 1 | 1);
    tree[k] = tree[k << 1] + tree[k << 1 | 1];
}
void pushdown(ll l,ll r,ll k)
{
    tree[k << 1] = (tree[k << 1] * tagm[k] + taga[k] * (ri[k << 1] - le[k << 1] + 1)) % m;
    tree[k << 1 | 1] = (tree[k << 1 | 1] * tagm[k] + taga[k] * (ri[k << 1 | 1] - le[k << 1 | 1] + 1)) % m;
    tagm[k << 1] = (tagm[k << 1] * tagm[k]) % m;
    tagm[k << 1 | 1] = (tagm[k << 1 | 1] * tagm[k]) % m;
    taga[k << 1] = (taga[k << 1] * tagm[k] + taga[k]) % m;
    taga[k << 1 | 1] = (taga[k << 1 | 1] * tagm[k] + taga[k]) % m;
    tagm[k] = 1;
    taga[k] = 0; 
}
ll find(ll x,ll y,ll l,ll r,ll k)
{
    if(r < x || l > y) return 0;
    if(l >= x && r <= y) return tree[k];
    ll mid = l + r >> 1;
    pushdown(l,r,k);
    return find(x,y,l,mid,k << 1) + find(x,y,mid + 1,r,k << 1 | 1);
}
void change1(ll x,ll y,ll l,ll r,ll k,ll v)
{
    if(r < x || l > y) return;
    if(l >= x && r <= y){
        tree[k] += v * (r - l + 1);
        tree[k] %= m;
        taga[k] += v;
        taga[k] %= m;
        return;
    }
    ll mid = l + r >> 1;
    pushdown(l,r,k);
    change1(x,y,l,mid,k << 1,v);
    change1(x,y,mid + 1,r,k << 1 | 1,v);
    tree[k] = tree[k << 1] + tree[k << 1 | 1];
}
void change2(ll x,ll y,ll l,ll r,ll k,ll v)
{
    if(r < x || l > y) return;
    if(l >= x && r <= y){
        tree[k] *= v;;
        tree[k] %= m;
        taga[k] *= v;
        taga[k] %= m;
        tagm[k] *= v;
        tagm[k] %= m;
        return;
    }
    ll mid = l + r >> 1;
    pushdown(l,r,k);
    change1(x,y,l,mid,k << 1,v);
    change1(x,y,mid + 1,r,k << 1 | 1,v);
    tree[k] = tree[k << 1] + tree[k << 1 | 1];
}
int main()
{
    scanf("%lld%lld%lld",&n,&q);
    for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
    buildtree(1,n,1);
    for(int i = 1;i <= q;i++){
        scanf("%lld",&f);
        if(f == 1) scanf("%lld%lld%lld",&x,&y,&k),change2(x,y,1,n,1,k);
        if(f == 2) scanf("%lld%lld%lld",&x,&y,&k),change1(x,y,1,n,1,k);
        if(f == 3) scanf("%lld%lld",&x,&y),cout << find(x,y,1,n,1) << "\n";
    }
 	return 0;
}